計數(shù)排序與基數(shù)排序

計數(shù)排序

計數(shù)排序：使用一個數(shù)組記錄序列中每一個數(shù)字出現(xiàn)的次數(shù)，將該數(shù)組的下標(biāo)作為實際數(shù)據(jù)，元素的值作為數(shù)據(jù)出現(xiàn)的次數(shù)。例如對于序列[3,0,1,1,3,3,0,2]，統(tǒng)計的結(jié)果為：

0出現(xiàn)的次數(shù)：2次
1出現(xiàn)的次數(shù)：2次
2出現(xiàn)的次數(shù)：1次
3出現(xiàn)的次數(shù)：3次

依據(jù)出現(xiàn)的次數(shù)就可以構(gòu)建出排序之后的序列

void CountSort(vector<int>& nums) {int minNum = nums.front();int maxNum = nums.front();for (int num : nums) {minNum = std::min(minNum, num);maxNum = std::max(maxNum, num);}int helpSize = maxNum - minNum + 1;int* help = new int[helpSize] {0};//例如最大值為10，最小值為5，需要開辟的數(shù)組大小是10-5+1for (int num : nums) {help[num - minNum]++;//統(tǒng)計次數(shù)}nums.clear();for (int i = 0; i < helpSize; i++) {while (help[i]--) {nums.push_back(i + minNum);}}delete[] help;
}

計數(shù)排序的時間復(fù)雜度和空間復(fù)雜度

時間復(fù)雜度：O(N+max-min)，其中max為數(shù)組中的最大元素，min為數(shù)組中的最小元素。計數(shù)排序需要遍歷原數(shù)組一趟，得到原數(shù)組的最大值和最小值從而決定需要開辟的輔助數(shù)組的大小，還需要遍歷輔助數(shù)組得到有序序列

空間復(fù)雜度：O(max-min)，取決于數(shù)組中最大值和最小值的差

計數(shù)排序適用于數(shù)據(jù)量很大，但是數(shù)據(jù)分布比較密集的場景，例如有1億個數(shù)，它們都在[20,1000]范圍，此時就可以使用計數(shù)排序，與其它排序算法相比（例如快排、冒泡），計數(shù)排序是一種非比較排序

基數(shù)排序

在計數(shù)排序中，對于數(shù)據(jù)較為分散的場景，所需開辟的額外空間較大，例如序列[1,56,26,9999,7]，若使用計數(shù)排序，需要額外開辟一個大小為9999的數(shù)組，但是原數(shù)組只有5個數(shù)需要進(jìn)行排序，在這種情況下，可以考慮使用基數(shù)排序

基數(shù)排序也是一種非比較排序，基本思想是：先將原序列按照個位進(jìn)行排序，在按照十位進(jìn)行排序……依次類推，直到序列完全有序，以[1,56,26,9999,7]為例，流程如下：

基數(shù)排序的輪數(shù)取決于序列中最大值的位數(shù)，在進(jìn)行基數(shù)排序時，位數(shù)小的數(shù)字一定在位數(shù)大的數(shù)字的前面，例如上圖中7雖然在進(jìn)行第一輪排序完成后處于56的后面，但是當(dāng)完成第二輪排序后7處于56的前面，因為7的十位為0

如何提取一個數(shù)字的個位、十位、百位？

方案一：使用to_string將該數(shù)字轉(zhuǎn)化為字符串，依次進(jìn)行提取

方案二：定義一個offset變量，初始為1，將(num/offset)%10，得到個位，每進(jìn)行一輪，將offset*10

int num = 3675;
int offset = 1;
int bitNum;
while (bitNum=num / offset) {cout << bitNum % 10 << ' ';offset *= 10;
}
cout << endl;

基數(shù)排序的桶

在進(jìn)行基數(shù)排序時一般使用隊列作為基數(shù)排序的桶，對10進(jìn)制數(shù)字進(jìn)行排序就需要準(zhǔn)備9個隊列

void RadixSortByQueue(vector<int>& nums, int bits, int BASE = 10) {//使用隊列作為桶進(jìn)行基數(shù)排序//bits表示序列中的最大值的位數(shù)//BASE表示多少進(jìn)制vector<queue<int>> Queues;Queues.resize(BASE);int offset = 1;for (int offset = 1; bits > 0; bits--, offset *= BASE) {//例如最大值為156，則進(jìn)行3輪for (int num : nums) {int bitNum = (num / offset) % BASE;//得到個位/十位/百位……的數(shù)Queues[bitNum].push(num);}//按照個位/十位/百位……排好的數(shù)已經(jīng)放入Queues中nums.clear();for (auto& Queue : Queues) {while (!Queue.empty()) {nums.push_back(Queue.front());Queue.pop();}}}
}

基數(shù)排序的優(yōu)化

前綴數(shù)量分區(qū)：以序列[1,56,26,9999,7]為例，個位數(shù)分別是1,6,6,9,7，可以得到的前綴信息如下

個位數(shù)<=1的數(shù)據(jù)數(shù)量:1
個位數(shù)<=6的數(shù)據(jù)數(shù)量:3
個位數(shù)<=7的數(shù)據(jù)數(shù)量:4
個位數(shù)<=9的數(shù)據(jù)數(shù)量:5

那么在每一輪按照特定位進(jìn)行排序時就不需要使用隊列，直接開一個和原始數(shù)組等規(guī)模的輔助數(shù)組help即可，將[1,56,26,9999,7]按照個位進(jìn)行排序，對于數(shù)字7，個位為7，由于個位數(shù)<=7的數(shù)據(jù)數(shù)量是4，所以7直接放到help數(shù)組中下標(biāo)為3的位置，此時原序列中的7已經(jīng)放到help數(shù)組中，原序列中個位數(shù)<=7的數(shù)據(jù)數(shù)量減少一個，變?yōu)?，以此類推，直到原序列中的數(shù)據(jù)全部按照規(guī)則轉(zhuǎn)移到help數(shù)組中，此時help數(shù)組中的數(shù)據(jù)就是按照位排序好的數(shù)據(jù)

void RadixSort(vector<int>& nums, int bits, int BASE = 10) {//bits表示序列中的最大值的位數(shù)//BASE表示多少進(jìn)制int* counts = new int[BASE] {0};int* help = new int[nums.size()]{ 0 };int offset = 1;for (int offset = 1; bits > 0; bits--, offset *= BASE) {memset(counts, 0, sizeof(int) * BASE);for (int num : nums) {int bitNum = (num / offset) % BASE;counts[bitNum]++;//先統(tǒng)計個數(shù)}for (int i = 1; i < BASE; i++) {counts[i] += counts[i - 1];//統(tǒng)計前綴數(shù)量}for (int i = nums.size() - 1; i >= 0; i--) {int bitNum = (nums[i] / offset) % BASE;help[--counts[bitNum]] = nums[i];}memcpy(nums.data(), help, sizeof(int) * nums.size());}delete[] help;delete[] counts;
}

為什么需要從后往前遍歷向help數(shù)組中填數(shù)據(jù)？

以[1,99,7]為例，在排個位數(shù)時，可以從后往前，也可以從前往后，沒有影響，個位數(shù)排完之后，得到[1,7,99]，但是在排十位數(shù)時，必須從后往前，否則就會打亂1和7的順序，因為1和7的十位都是0，十位<=0的數(shù)的個數(shù)是2,7是最后一個十位<=的數(shù)，因此在遍歷時需要從后往前遍歷排到靠后位置.

基數(shù)排序的拓展

如果原序列中存在負(fù)數(shù)，如何進(jìn)行基數(shù)排序？

將原序列中的所有數(shù)字加上最小值的絕對值，在進(jìn)行基數(shù)排序，將排完序的結(jié)果在減去原來最小值的絕對值。如果存在溢出問題，需要考慮使用long long類型。

void RadixSortContainMinus(vector<int>& nums, int BASE = 10) {int minNum = nums[0];for (int num : nums) {minNum = std::min(minNum, num);}int maxNum = 0;for (int& num : nums) {num -= minNum;maxNum = std::max(maxNum, num);}int bits = 1;while (maxNum / BASE) {bits++;maxNum /= BASE;}RadixSort(nums, bits, BASE);for (int& num : nums) {num += minNum;}
}

如果需要排序的數(shù)字不是十進(jìn)制，如何使用基數(shù)排序?qū)崿F(xiàn)？

若需要排序的數(shù)字不是10進(jìn)制，只需要修改BASE即可，其它思路一致，例如需要排序的數(shù)字是16進(jìn)制，那么counts數(shù)組的大小定為16即可，統(tǒng)計每一位在0~f的數(shù)量，依然使用前綴分區(qū)技巧

基數(shù)排序的時間復(fù)雜度

基數(shù)排序的時間復(fù)雜度為O(m*n)，其中m表示原序列中最大值的位數(shù)，n表示數(shù)據(jù)量，因為要根據(jù)位數(shù)確定排多少輪?；鶖?shù)排序的空間復(fù)雜度為O(m+n)，需要使用一個help數(shù)組和一個counts數(shù)組，其中counts數(shù)組用于統(tǒng)計個數(shù)，help數(shù)組用于進(jìn)行保存這一輪排序完畢的數(shù)據(jù).