- 中文名
- 计数排序
- 外文名
- Counting Sort
- 提出人
- Harold H. Seward
- 提出时间
- 1954年
- 定 义
- 非基于比较的排序算法
计数排序对输入的数据有附加的限制条件：
2、设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。
在这两个条件下，计数排序的复杂性为O(n)。
计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。
假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序可以描述如下：
2、扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。
PASCAL语言描述
实现方法1：
program counting_sort1;
var
a,b,c:Array[1..max] of longint;
i,j,k,n:longint;
begin
readln(n);
for i:=1 to n do read(a[i]);
fillchar(c,sizeof(c),0);
for j:=1 to n do inc(c[a[j]]);
for i:=2 to x{x是大于a[i]中任意值的任意数且x≤max}do c[i]:=c[i]+c[i-1];
for j:=n downto 1 do
begin
b[c[a[j]]]:=a[j];
dec(c[a[j]]);
end;
for i:=1 to n do writeln(b[i],' ');
end.
实现方法2：
program counting_sort2;
const max=100;
var
a:array[1..max] of longint;
i,j,k,n,m,x:longint;
begin
readln(n);
fillchar(a,sizeof(a),0);//初始清空
m:=0;
for i:=1 to n do
begin
read(x);
inc(a[x]);
if x>m then m:=x;//找到最大的数
end;
for i:=1 to m do
if a[i]>0 then
for j:=1 to a[i] do
write(i,' ');
end.
C++语言描述
#include <iostream>
using namespace std;
const int MAXN = 100000;
const int k = 1000; // range(范围)
int a[MAXN], c[MAXN], ranked[MAXN];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
++c[a[i]];
}
for (int i = 1; i < k; ++i)
c[i] += c[i-1];
for (int i = n-1; i >= 0; --i)
ranked[--c[a[i]]] = a[i];//如果是i表达的是原数标号，a[i]就是排序后的正确序列
for (int i = 0; i < n; ++i)
cout << ranked[i] << endl;
return 0;
}
C语言实现
#include<stdio.h>
#include<stdlib.h>
#define MAXNUM 10
void main()
{
void CountSort(int data[],int n);
int i,data[MAXNUM];
for(i=0;i<MAXNUM;i++)
scanf("%d",&data[i]);
CountSort(data,MAXNUM);
for(i=0;i<MAXNUM;i++)
printf("%d ",data[i]);
printf("\n");
}
void CountSort(int data[],int n)
{
int i,j,count,*data_p,temp;
data_p=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++)//初始化data_p
data_p[i]=0;
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)//扫描待排序数组
if(data[j]<data[i])//统计比data[i]值小的值的个数
count++;
while(data_p[count]!=0)//对于相等非0的数据，应向后措一位。数据为0时，因数组data_p被初始化为0，故不受影响。
/* 注意此处应使用while循环进行判断，若用if条件则超过三个重复值后有0出现 */
count++;
data_p[count]=data[i];//存放到data_p中的对应位置
}
//用于检查当有多个数相同时的情况
i=0,j=n;
while(i<j)
{
if(data_p[i]==0)
{
temp=i-1;
data_p[i]=data_p[temp];
}//of if
i++;
}//of while
for(i=0;i<n;i++)//把排序完的数据复制到data中
data[i]=data_p[i];
free(data_p);//释放data_p
}
JAVA语言描述
//针对c数组的大小，优化过的计数排序
publicclassCountSort{
publicstaticvoidmain(String[]args){
//排序的数组
int a[]={100,93,97,92,96,99,92,89,93,97,90,94,92,95};
int b[]=countSort(a);
for(inti:b){
System.out.print(i+"");
}
System.out.println();
}
public static int[] countSort(int[]a){
int b[] = new int[a.length];
int max = a[0],min = a[0];
for(int i:a){
if(i>max){
max=i;
}
if(i<min){
min=i;
}
}//这里k的大小是要排序的数组中，元素大小的极值差+1
int k=max-min+1;
int c[]=new int[k];
for(int i=0;i<a.length;++i){
c[a[i]-min]+=1;//优化过的地方，减小了数组c的大小
}
for(int i=1;i<c.length;++i){
c[i]=c[i]+c[i-1];
}
for(int i=a.length-1;i>=0;--i){
b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
}
return b;
}
}
C#语言描述
public int[] CountSort(int[] a)
{
int[] b = new int[a.Length];
int max = a[0];
int min = a[0];
foreach (int item in a)
{
if(item > max)
{
max = item;
}
else if (item < min)
{
min = item;
}
}
int k = max - min + 1;
int[] c = new int[k];
for (int i = 0; i < a.Length; i++)
{
c[a[i] - min] += 1;
}
for (int i = 1; i < c.Length; i++)
{
c[i] = c[i] + c[i - 1];
}
for (int i = a.Length-1; i >= 0; i--)
{
b[--c[a[i] - min]] = a[i];
}
return b;
}
python语言描述
def count_sort(input_list):
length = len(input_list)
if length < 2:
return input_list
max_num = max(input_list)
count = [0] * (max_num + 1)
for element in input_list:
count[element] += 1
output_list = []
for i in range(max_num + 1):
for j in range(count[i]): # count[i]表示元素i出现的次数，如果有多次，通过循环重复追加
output_list.append(i)
return output_list
GO语言描述
func countSort(arr []int) {
maxVal := 0
length := len(arr)
for i := 0; i < length; i ++ {
if arr[i] > maxVal {
maxVal = arr[i]
}
}
tmp := make([]int, maxVal+1)
for i := 0; i < length; i ++ {
tmp[arr[i]] += 1
}
j := 0
for i := 0; i < maxVal+1; i ++ {
for tmp[i] > 0 {
arr[j] = i
j ++
tmp[i] --
}
}
}
我们看到，计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而它的计算时间下界不再是O(nlogn)。另一方面，计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制，即k=O(n)。如果k=n^2,n^3,..，就得不到线性时间的上界。此外，我们还看到，由于算法第4行使用了downto语句，经计数排序，输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同，换句话说，计数排序算法是一个稳定的排序算法。
优化前向星
一开始读入时，先算出每个点出去的边有多少条，然后计算出排序后每个点出去的第一条边位置应在哪里，最后把全部边扫一遍放到排序后应在的位置就好了。
