三种线性排序算法

计数排序

首先从计数排序(Counting Sort)开始介绍起，假设我们有一个待排序的整数序列A，其中元素的最小值不小于0，最大值不超过k。建立一个长度为K的线性表count，用来记录不大于每个值的元素的个数。

算法思路如下：

• 1、扫描序列A，以A中的每个元素的值为索引，把出现的个数填入count中。此时count[i]可以表示A中值为i的元素的个数。
• 2、对于count从头开始累加，使count[i]<-count[i]+count[i-1]。这样，count[i]就表示A中值不大于i的元素的个数。
• 3、按照统计出的值，输出结果。

#include <vector>
using namespace std;

vector<int>  CountingSort(vector<int> A,  int k){
    vector<int> count(k), res(A.size());
    int size = A.size(), i = 0;
    for (i = 0; i < size; i++) //计算每个元素的个数
        count[A[i]]++;
    for (i = 1; i < k; i++) //统计不大于i的元素的个数
        count[i] += count[i - 1];
    for (i = size - 1; i >= 0; i--){
        res[count[A[i]] - 1] = A[i]; //按照统计的位置，将值输出到res中
        count[A[i]]--;
    }
    return res;
}

int main(){
    vector<int> res = CountingSort({ 2, 2, 2, 4, 4, 1, 1, 4, 5, 6, 7, 7, 8},  9);
    return 0;
}

桶排序

可能你会发现，计数排序似乎饶了点弯子，比如当我们刚刚统计出count，count[i]可以表示A中值为i的元素的个数，此时我们直接顺序地扫描C，就可以求出排序后的结果。的确是这样，不过这种方法不再是计数排序，而是桶排序(Bucket Sort)，确切地说，是桶排序的一种特殊情况。

#include <vector>
using namespace std;

vector<int>  BucketSort(vector<int> A, int k){
    vector<int> count(k), res(A.size());
    int size = A.size();
    for (int i = 0; i < size; i++) //计算每个元素的个数
        count[A[i]]++;
    for (int i = 0, j = 0; i < k; ++i)
        while (count[i]--) res[j++] = i;
    return res;
}

int main(){
    vector<int> res = BucketSort({ 2, 2, 2, 4, 4, 1, 1, 4, 5, 6, 7, 7, 8},  9);
    return 0;
}

基数排序

上述的基数排序和桶排序都只是在研究一个关键字的排序，现在我们来讨论有多个关键字的排序问题。

假设我们有一些二元组(a,b)，要对它们进行以a为首要关键字，b的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。

第二种方式是从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD方法往往比MSD简单而开销小。

下面是LSD的实现：

int maxbit(int data[], int n){ //辅助函数，求数据的最大位数
    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i){
        while(data[i] >= p) {
            p *= 10;
            ++d;
        }
    }
    return d;
}

void radixsort(int data[], int n){ //基数排序
    int d = maxbit(data, n);
    int *tmp = newint[n];
    int *count = newint[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) {//进行d次排序
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++){
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) { //将所有桶中记录依次收集到tmp中
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete[]tmp;
    delete[]count;
}

参考文献：
1、三种线性排序算法 计数排序、桶排序与基数排序
2、基数排序