计数排序

计数排序

  计数排序的思想在于统计比某个数小或等于它的个数。关键就在于统计,就随便举一个例子

有一个要从小到大排序的数组A[] = {3,4,1,5, 6}

如何确定比A[0]小的个数

定一个数组counter,counter用来统计,方法是这样的↓

将每个元素对应counter的下标,counter这个位加一,counter[A[i]]++

这样操作完了,counter数组变成了这样

pos  0  1  2  3  4  5  6  7  8

val  0  1  0  1  1  1  1  0  0

好像并不能直观地通过值来看出A[0]小的个数

但是如果想前缀和一样,从前往后加会发生什么情况?

pos  0  1  2  3  4  5  6  7  8

val  0  1  1  2  3  4  5  5  5

小于等于x的数(包括自己)就是counter[x]个

稍微想一下就能理解

按照这个数组把原数组中的元素拷贝到另一个数组里就行了

  按照这样做应该只能得个十二十分吧,因为貌似这样做对像下面这组数据不是

特别地灵

1 3 3 4 5

  另一个数组中的值应该是这样的

1 0 3 4 5

  这说明上面并不是完整的计数排序,还差在哪呢?拷贝的时候把counter对应位上

减一就行了(下次拷贝这个数就放在刚刚这个数的位置的前一个)

Code

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int* sorted;
 5 int* counter;
 6 void CountingSort(int *array, int len){
 7     sorted = new int[(const int)(len)];
 8     int maxv = array[0]; 
 9     int minv = array[0];
10     for(int i = 1;i < len;i++){        //找出最大值和最小值,当然可以不这么做 
11         maxv = max(array[i], maxv);    //counter数组定一个足够大的大小就行了 
12         minv = min(array[i], minv);
13     }
14     counter = new int[(const int)(maxv + 1)];    //如果想省点内存还可以写成(maxv - minv + 2),下面改一下就行了 
15     memset(counter, 0, sizeof(int) * (maxv + 1));
16     for(int i = 0;i < len;i++){
17         counter[array[i]]++;            //计数 
18     }
19     for(int i = minv + 1;i <= maxv;i++){
20         counter[i] += counter[i - 1];    //累加得到小于等于i的个数 
21     }
22     for(int i = len - 1;i >= 0;i--){    //拷贝,这里也可以从1循环到len - 1 
23         sorted[--counter[array[i]]] = array[i]; 
24     }
25 }
26 int n;
27 int *list;
28 int main(){
29     cin>>n;
30     list = new int[(const int)(n + 1)];
31     for(int i = 0;i < n;i++)
32         cin>>list[i];
33     CountingSort(list, n);
34     for(int i = 0;i < n;i++)
35         cout<<sorted[i]<<" ";
36     return 0;
37 }