计数排序
首先从计数排序(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、基数排序
