文章目錄

• • 復習梗概
  • 算法思想
  • • 基礎思想
    • 改進空間復雜度，改進不能對負數進行排序問題
    • 改進穩定性
  • 計數排序時間空間復雜度
  • 計數排序基礎版 代碼及輸出
  • 計數排序第一次改進版 代碼及輸出
  • 計數排序終極版 代碼及輸出（重要）
  • 完整版代碼

復習梗概

基礎算法思想？

兩種改進的思路？重點在于最終版本思想

最終版本是如何做到穩定的？

三個數組（array，counts，temp）彼此間的索引和元素的對應關系？

---

算法思想

基礎思想

計數排序適合對在一定范圍內的整數進行排序

先找到排序數組的最大值，創建一個最大索引是該最大值的計數數組，初始值全部為0，然后對排序數組進行計數，若元素i出現了一次，就在計數數組的對應i索引處元素+1，全部計數后，只要按照計數數組的索引（原排序數組的元素）和對應的元素（原排序數組元素出現的次數）按順序輸出索引和對應的元素（即輸出原元素和其出現的次數）即可
圖片來自網課戀上數據結構與算法，騰訊課堂

---

改進空間復雜度，改進不能對負數進行排序問題

但是如果按照上述實現，會造成三個問題：1.不是穩定排序 2.及其浪費內存空間，前面0到最小值部分都用不上 3.無法對負整數進行排序，因為計數數組索引只能是正數

初步改進計數排序：同時查找排序數組的最大值和最小值（max and min），開辟空間為max-min+1的容量的數組，此時排序元素與計數數組的索引的對應關系：計數索引+min，即為原排序元素

如下圖，為counts數組打印結果，注意索引以及經過+min處理，代表原排序元素

---

改進穩定性

即使經過上面的改進依然不能做到穩定的排序，是因為我們按照 計數數組 的索引與次數 輸出排序數組，無論如何都做不到穩定，因為兩個相同的元素在 計數數組 的索引中是體現不出來區別的。

所以我們從根本上改變了思想，不按照技術數組簡單輸出，并做出如下改變

依然通過max和min創建計數數組，但計數時，把技術數組的次數變為累加值，即 包括自己在內前面所有元素出現次數的累加和 ；這是，如果累加次數值 為8，就意味著該元素在排序數組中 應該排在第8位

輸出數組時，新定義一個和未排序數組大小相同的數組，因為我們一會要用到未排序數組，所以先備份一個

利用未排序數組 和 計數數組，從最右側向最左側遍歷，遍歷到一個元素，先找到其對應在計數數組中的 累加次數值 x（即該元素排序位置），就把其覆蓋到備份數組中 x-1的索引處，同時 累加次數值-1（這樣若左邊還有相同元素，下次就會覆蓋到前一個位置，就穩定了）

遍歷完成，覆蓋完成，排序完成，備份數組覆蓋原未排序數組即可。
圖片來自網課戀上數據結構與算法，騰訊課堂

計數排序時間空間復雜度

最好最壞平均時間復雜度：O（n+k）其中n為排序數組長度，k為max-min+1（計數數組長度）

空間復雜度O（n+k），來自計數數組和備份數組

因為不是比較排序，所以最好最壞平均時間復雜度都一樣

屬于空間換時間的典例

---

計數排序基礎版 代碼及輸出

比較簡單，直接看后面改進版把 void countingSort(vector<int> &array) {int max = array[0];for(int index = 1;index<array.size();index++){if(max<array[index]){max = array[index];}}int* counts = new int[max+1]{0};for(int index = 0;index<array.size();index++){counts[array[index]]++;}vector<int> sortedArray;for(int index = 0;index <=max;index++){for(int i = 0;i<counts[index];i++){sortedArray.push_back(index);}}array = sortedArray; } 輸入數組： 6 9 6 7 5 8 8 29 15 11 10 計數排序基礎版 索引 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 次數 0 0 0 0 0 1 2 1 2 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 算法用時：（微秒） [AlgoTime: 6001 us] 排序結果： 5 6 6 7 8 8 9 10 11 15 29

---

計數排序第一次改進版 代碼及輸出

void countingSort2nd(vector<int> &array){//遍歷排序數組，記錄最大值與最小值int max = array[0];int min = array[0];for(int i = 1;i<array.size();i++){if(max<array[i]){max = array[i];}if(min>array[i]){min = array[i];}}//創建計數數組，長度為max-min+1，記住創建數組【】里的是長度，不是最大索引int *counts = new int[max - min + 1]{0};//進行計數，以及計數結果顯示for(int i = 0;i<array.size();i++){counts[array[i]-min]++;}//按照計數數組，對array進行重置int arrayIndex = 0;for(int i = 0;i<max-min+1;i++){while (counts[i]-->0){array[arrayIndex] = i+min;arrayIndex++;}} } 輸入數組： -6 9 6 7 5 8 8 29 15 11 10 計數排序基礎版 索引 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 次數 1 0 0 0 0 0 0 0 0 0 0 1 1 1 2 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 算法用時：（微秒） [AlgoTime: 7003 us] 排序結果： -6 5 6 7 8 8 9 10 11 15 29

---

計數排序終極版 代碼及輸出（重要）

void countingSort3rd(vector<int> &array){//遍歷未排序數組，記錄最大最小值int min = array[0];int max = array[0];for(int i = 1; i<array.size();i++){if(min>array[i]){min = array[i];}if(max <array[i]){max = array[i];}}//定義計數數組，進行計數int* counts = new int [max -min +1]{0};for(int i = 0;i<array.size();i++){counts[array[i]-min]++;}//在原有計數數組的基礎，對計數值進行累加，把計數值改為 該元素在排序數組中的位置int locatingNum = 0;for(int i = 0;i<max-min+1;i++){if(counts[i] == 0){//如果排序數組中沒有這個元素（計數值為0），不進行累加continue;}locatingNum = locatingNum + counts[i];counts[i] = locatingNum;}//打印累加計數數組countsIndexPrint(min,max);cout<<endl;arrayPrint(counts,max-min+1); //定義臨時數組，根據累加計數數組的位置值，從右到左遍歷未排序數組，把元素插入到對應位置int* temp = new int[array.size()];for(int index = array.size()-1;index>=0;index--){//array[index]-min = counts數組對應元素索引//counts[數組對應元素索引] = 數組對應元素在排序序列中的位置//counts[數組對應元素索引] - 1 = 數組對應元素在排序數組中的索引temp[counts[array[index]-min]-1] = array[index];counts[array[index]-min]--;}//用備份數組覆蓋原數組for (int i = 0; i < array.size(); i++){array[i]=temp[i];} } 輸入數組： -6 9 6 7 5 8 8 29 15 11 10 計數排序終極版 索引 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 累加次數 1 0 0 0 0 0 0 0 0 0 0 2 3 4 6 7 8 9 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 11 算法用時：（微秒） [AlgoTime: 6000 us] 排序結果： -6 5 6 7 8 8 9 10 11 15 29

---

完整版代碼

#include <iostream> #include <vector> #include "MeasureAlgoTime.hpp" using namespace std;void vectorPrint(vector<int> &array) {for (int i = 0; i < array.size(); i++){cout << array[i] << ' ';}cout << endl; }void arrayPrint(int array[],int length){cout<<"次數"<<" ";for(int i = 0;i<length;i++){cout<<array[i]<<" ";} }void countsIndexPrint(int min,int max){cout<<"索引"<<" ";for(int i =min;i<=max;i++){cout<<i<<" ";} }void countingSort(vector<int> &array) {int max = array[0];for(int index = 1;index<array.size();index++){if(max<array[index]){max = array[index];}}int* counts = new int[max+1]{0};for(int index = 0;index<array.size();index++){counts[array[index]]++;}countsIndexPrint(0,max);cout<<endl;arrayPrint(counts,max-0+1);vector<int> sortedArray;for(int index = 0;index <=max;index++){for(int i = 0;i<counts[index];i++){sortedArray.push_back(index);}}array = sortedArray; }void countingSort2nd(vector<int> &array){//遍歷排序數組，記錄最大值與最小值int max = array[0];int min = array[0];for(int i = 1;i<array.size();i++){if(max<array[i]){max = array[i];}if(min>array[i]){min = array[i];}}//創建計數數組，長度為max-min+1，記住創建數組【】里的是長度，不是最大索引int *counts = new int[max - min + 1]{0};//進行計數，以及計數結果顯示for(int i = 0;i<array.size();i++){counts[array[i]-min]++;}countsIndexPrint(min,max);cout<<endl;arrayPrint(counts,max-min+1);//按照計數數組，對array進行重置int arrayIndex = 0;for(int i = 0;i<max-min+1;i++){while (counts[i]-->0){array[arrayIndex] = i+min;arrayIndex++;}} }void countingSort3rd(vector<int> &array){//遍歷未排序數組，記錄最大最小值int min = array[0];int max = array[0];for(int i = 1; i<array.size();i++){if(min>array[i]){min = array[i];}if(max <array[i]){max = array[i];}}//定義計數數組，進行計數int* counts = new int [max -min +1]{0};for(int i = 0;i<array.size();i++){counts[array[i]-min]++;}//在原有計數數組的基礎，對計數值進行累加，把計數值改為 該元素在排序數組中的位置int locatingNum = 0;for(int i = 0;i<max-min+1;i++){if(counts[i] == 0){//如果排序數組中沒有這個元素（計數值為0），不進行累加continue;}locatingNum = locatingNum + counts[i];counts[i] = locatingNum;}//打印累加計數數組countsIndexPrint(min,max);cout<<endl;arrayPrint(counts,max-min+1); //定義臨時數組，根據累加計數數組的位置值，從右到左遍歷未排序數組，把元素插入到對應位置int* temp = new int[array.size()];for(int index = array.size()-1;index>=0;index--){//array[index]-min = counts數組對應元素索引//counts[數組對應元素索引] = 數組對應元素在排序序列中的位置//counts[數組對應元素索引] - 1 = 數組對應元素在排序數組中的索引temp[counts[array[index]-min]-1] = array[index];counts[array[index]-min]--;}//用備份數組覆蓋原數組for (int i = 0; i < array.size(); i++){array[i]=temp[i];} }int main() {Tools::Time::AlgoTimeUs time1;Tools::Time::AlgoTimeUs time2;Tools::Time::AlgoTimeUs time3;vector<int> array;array = {6, 9, 6, 7, 5, 8, 8, 29, 15, 11, 10};vector<int> array2 = {-6, 9, 6, 7, 5, 8, 8, 29, 15, 11, 10};vector<int> array3 = array2;cout<<"輸入數組："<<endl;vectorPrint(array);time1.start();cout << "計數排序基礎版" << endl;countingSort(array);cout << "算法用時：（微秒）";time1.printElapsed();cout << "排序結果：" << endl;vectorPrint(array);cout << ' ' << endl;cout<<"輸入數組："<<endl;vectorPrint(array2);time2.start();cout << "計數排序第一次改進版" << endl;countingSort2nd(array2);cout <<endl<< "算法用時：（微秒）";time2.printElapsed();cout << "排序結果：" << endl;vectorPrint(array2);cout << ' ' << endl;cout<<"輸入數組："<<endl;vectorPrint(array3);time3.start();cout << "計數排序終極版" << endl;countingSort3rd(array3);cout <<endl<< "算法用時：（微秒）";time3.printElapsed();cout << "排序結果：" << endl;vectorPrint(array3);cout << ' ' << endl;return 0; }

總結

以上是生活随笔為你收集整理的计数排序及其改进 C++代码实现与分析 恋上数据结构笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。