計(jì)數(shù)排序
首先從計(jì)數(shù)排序(Counting Sort)開始介紹起茬末，假設(shè)我們有一個(gè)待排序的整數(shù)序列A，其中元素的最小值不小于0盖矫，最大值不超過k丽惭。建立一個(gè)長度為K的線性表count，用來記錄不大于每個(gè)值的元素的個(gè)數(shù)辈双。
算法思路如下：
- 1责掏、掃描序列A，以A中的每個(gè)元素的值為索引湃望，把出現(xiàn)的個(gè)數(shù)填入count中换衬。此時(shí)count[i]可以表示A中值為i的元素的個(gè)數(shù)。
- 2证芭、對于count從頭開始累加瞳浦，使count[i]<-count[i]+count[i-1]。這樣废士，count[i]就表示A中值不大于i的元素的個(gè)數(shù)叫潦。
- 3、按照統(tǒng)計(jì)出的值湃密，輸出結(jié)果诅挑。
#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++) //計(jì)算每個(gè)元素的個(gè)數(shù)
count[A[i]]++;
for (i = 1; i < k; i++) //統(tǒng)計(jì)不大于i的元素的個(gè)數(shù)
count[i] += count[i - 1];
for (i = size - 1; i >= 0; i--){
res[count[A[i]] - 1] = A[i]; //按照統(tǒng)計(jì)的位置，將值輸出到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;
}
桶排序
可能你會發(fā)現(xiàn)泛源，計(jì)數(shù)排序似乎饒了點(diǎn)彎子拔妥，比如當(dāng)我們剛剛統(tǒng)計(jì)出count，count[i]可以表示A中值為i的元素的個(gè)數(shù)达箍，此時(shí)我們直接順序地掃描C没龙，就可以求出排序后的結(jié)果。的確是這樣缎玫，不過這種方法不再是計(jì)數(shù)排序硬纤，而是桶排序(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++) //計(jì)算每個(gè)元素的個(gè)數(shù)
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;
}
基數(shù)排序
上述的基數(shù)排序和桶排序都只是在研究一個(gè)關(guān)鍵字的排序，現(xiàn)在我們來討論有多個(gè)關(guān)鍵字的排序問題邻辉。
假設(shè)我們有一些二元組(a,b)溪王，要對它們進(jìn)行以a為首要關(guān)鍵字，b的次要關(guān)鍵字的排序莹菱。我們可以先把它們先按照首要關(guān)鍵字排序移国，分成首要關(guān)鍵字相同的若干堆。然后道伟，在按照次要關(guān)鍵值分別對每一堆進(jìn)行單獨(dú)排序迹缀。最后再把這些堆串連到一起，使首要關(guān)鍵字較小的一堆排在上面蜜徽。按這種方式的基數(shù)排序稱為MSD(Most Significant Dight)排序祝懂。
第二種方式是從最低有效關(guān)鍵字開始排序，稱為LSD(Least Significant Dight)排序娜汁。首先對所有的數(shù)據(jù)按照次要關(guān)鍵字排序嫂易，然后對所有的數(shù)據(jù)按照首要關(guān)鍵字排序。要注意的是掐禁，使用的排序算法必須是穩(wěn)定的怜械，否則就會取消前一次排序的結(jié)果。由于不需要分堆對每堆單獨(dú)排序傅事，LSD方法往往比MSD簡單而開銷小缕允。
下面是LSD的實(shí)現(xiàn)：
int maxbit(int data[], int n){ //輔助函數(shù)，求數(shù)據(jù)的最大位數(shù)
int d = 1; //保存最大的位數(shù)
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){ //基數(shù)排序
int d = maxbit(data, n);
int *tmp = newint[n];
int *count = newint[10]; //計(jì)數(shù)器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) {//進(jìn)行d次排序
for(j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空計(jì)數(shù)器
for(j = 0; j < n; j++){
k = (data[j] / radix) % 10; //統(tǒng)計(jì)每個(gè)桶中的記錄數(shù)
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個(gè)桶
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++) //將臨時(shí)數(shù)組的內(nèi)容復(fù)制到data中
data[j] = tmp[j];
radix = radix * 10;
}
delete[]tmp;
delete[]count;
}
參考文獻(xiàn)：
1蹭越、三種線性排序算法 計(jì)數(shù)排序障本、桶排序與基數(shù)排序
2、基數(shù)排序
