算法：排序（三）

计数排序与基数排序

利用桶排序的思想可以达到O(N)的时间复杂度，但仅限于特定的情况。

计数排序

已知数据取值在狭小且有限的集合内，则可以使用计数排序。思路是预先准备好表征元素取值的计数桶，遍历元素时，使得表征该元素取值的桶计数值加一。遍历完成后倒出元素即可。

int* countingSort(int* A, int n) {
    //获取最大最小值以便分配桶
    int min=A[0],max=A[0];
    for(int i=1;i<n;++i){
        if(A[i]>max)
            max=A[i];
        if(A[i]<min)
            min=A[i];
    }
    //分配桶：一个计数数组
    int* ss=new int[max-min+1]();
    //对每个元素找到其对应的桶
    for(int i=0;i<n;++i)
        ss[A[i]-min]++;
    //遍历所有的桶，把元素倒回去
    int pos=0;
    for(int i=0;i<max-min+1;++i){
        while(ss[i]--){
            A[pos++]=i+min;
        }
    }
    delete[] ss;
    return A;
}

基数排序

基数排序可以看做是计数排序的扩展。适用于元素有多个键值，键值取值狭小且有限的情况。思路是按照键值优先级从低到高进行排序。
举例：正整数的个位/十位/百位数字就是表征数字大小的各个键值，先按照个位数字放入各个桶内，然后倒出；再按照十位/百位数字继续此操作。

CODE

int* radixSort(int* A, int n) {
    const int M=10;
    //临时存储数据
    int* s=new int[n];
    //计数：每个键值各对应多少元素
    int* c=new int[M]();
    //被除数，用以计算当前位置的数字
    int x=1;
    int number;
    for(int t=0;t<5;++t){  //假设元素不超过五位数
        //清零计数数组
        for(int m=0;m<M;++m)
            c[m]=0;
        //统计数组中各个number的数目
        for(int i=0;i<n;++i){
            number=A[i]/x%10;
            c[number]++;
        }
        //c数组做累加操作
        for(int m=1;m<M;++m)
            c[m]=c[m-1]+c[m];
        //经过累加后，c[m]表示第m号桶的终止位置后一位
        //正是因此，我们放桶的时候从后往前放.
        for(int i=n-1;i>=0;--i){
            number=A[i]/x%10;
            s[--c[number]]=A[i];
        }
        //从桶中倒回数组
        for(int i=0;i<n;++i){
            A[i]=s[i];
        }
        x*=10;
    }
    delete[] s;
    delete[] c;
    return A;
}

注意

• 以上代码为了节省空间，所有的桶都位于数组s上的某一段，通过计数产生c数组，然后累加得到每个桶的尾后指针位置，以此访问桶。

  
  
• 元素入桶时根据尾后指针进行遍历，所以需要从后向前遍历数组。
• 如果不考虑空间花费，可以通过指针数组来创建类似于二维数组的结构来构造M个桶；或者使用队列等数据结构来处理。