文章目錄

• • 復習梗概
  • 算法思想
  • 時間及空間復雜度
  • 基數排序基礎版代碼 及輸出結果
  • • 計數排序函數
    • 基數排序函數
    • 可視化輸出
  • 另一種思路
  • 完整版代碼

復習梗概

思想

如何取數字各個位位數

計數排序保證穩定性怎么保證

算法思想

基數排序思想：本質是按照個位數字，十位數字，百位數字。。。分別對數組進行排序

在排序高位的時候，就把前面低位的最終順序完全確定了，直到排到最高位就完全確定順序
而因為每位數字都是0-9的范圍，又正好可以采用計數排序

思想不難，主要把思想轉換成代碼有一定難度，要注意如何取到每一位上的位數：個位：X/1%10 十位：X/10%10 百位：X/100%10

也要注意計數排序的寫法細節，以及在位數和原元素索引之間的轉換

輸入數組： 9 6 7 5 8 8 29 15 11 10 計數排序基礎版 計數數組【0-9】 次數 1 1 0 0 0 2 1 1 2 2 次數 1 2 0 0 0 4 5 6 8 10 按個位排序： 10 11 5 15 6 7 8 8 9 29 計數數組【0-9】 次數 6 3 1 0 0 0 0 0 0 0 次數 6 9 10 0 0 0 0 0 0 0 按十位排序： 5 6 7 8 8 9 10 11 15 29排序結果： 5 6 7 8 8 9 10 11 15 29

---

時間及空間復雜度

---

基數排序基礎版代碼 及輸出結果

計數排序函數

void countingSort(vector<int> &array,int radix){int * countArray = new int[10]{0}; //!計數數組，注意這里的10是數組長度，不是索引啊啊啊啊，和java一樣for(int i = 0;i<array.size();i++){countArray[array[i]/radix%10]++;}arrayPrint(countArray,10);cout<<endl;int locatingNum = 0; //!對計數數組的計數值進行累加，解決穩定性問題，詳情見計數排序筆記for(int i = 0;i<10;i++){if(countArray[i]==0){continue;}locatingNum = locatingNum+countArray[i];countArray[i] = locatingNum;}arrayPrint(countArray,10);cout<<endl;int * tempArray = new int[array.size()];//!根據計數數組，把數組有序地輸出到一個臨時數組for(int i = array.size()-1;i>=0;i--){//! 記得這里一定要從后往前遍歷，才能保證計數排序的穩定性！！！tempArray[countArray[array[i]/radix%10]-1] = array[i];countArray[array[i]/radix%10]--;}for(int i = 0;i<array.size();i++){//!用剛剛那個有序的臨時數組，覆蓋原數組array[i] = tempArray[i];}vectorPrint(array);cout<<endl;}

基數排序函數

主要就是確定最大位數，并按照位數進行計數排序

void radixSort(vector<int> &array){int maxNumIndex = 0;for(int i = 1;i<array.size();i++){ //!這里是找數組的最大值，確定計數排序的位數//!但是這里只考慮了數組內都是正整數的情況if(array[i]>array[maxNumIndex]){maxNumIndex = i;}}int max = array[maxNumIndex];for(int i = 1;i<=max;i = i*10){ //!按照個位，十位，百位。。。分別對數組進行計數排序countingSort(array,i);} }

可視化輸出

輸入數組： 9 6 7 5 8 8 29 15 11 10 計數排序基礎版 次數 1 1 0 0 0 2 1 1 2 2 次數 1 2 0 0 0 4 5 6 8 10 10 11 5 15 6 7 8 8 9 29次數 6 3 1 0 0 0 0 0 0 0 次數 6 9 10 0 0 0 0 0 0 0 5 6 7 8 8 9 10 11 15 29算法用時：（微秒） [AlgoTime: 6001 us] 排序結果： 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]<<" ";} }//!基數排序思想：本質是按照個位數字，十位數字，百位數字。。。分別對數組進行排序 //! 而因為每位數字都是0-9的范圍，又正好可以采用計數排序 //!思想不難，主要把思想轉換成代碼有一定難度，要注意如何取到每一位上的位數：個位：X/1%10 十位：X/10%10 百位：X/100%10 //!也要注意計數排序的寫法細節，以及在位數和原元素索引之間的轉換 void countingSort(vector<int> &array,int radix){int * countArray = new int[10]{0}; //!計數數組，注意這里的10是數組長度，不是索引啊啊啊啊，和java一樣for(int i = 0;i<array.size();i++){countArray[array[i]/radix%10]++;}arrayPrint(countArray,10);cout<<endl;int locatingNum = 0; //!對計數數組的計數值進行累加，解決穩定性問題，詳情見計數排序筆記for(int i = 0;i<10;i++){if(countArray[i]==0){continue;}locatingNum = locatingNum+countArray[i];countArray[i] = locatingNum;}arrayPrint(countArray,10);cout<<endl;int * tempArray = new int[array.size()];//!根據計數數組，把數組有序地輸出到一個臨時數組for(int i = array.size()-1;i>=0;i--){//! 記得這里一定要從后往前遍歷，才能保證計數排序的穩定性！！！tempArray[countArray[array[i]/radix%10]-1] = array[i];countArray[array[i]/radix%10]--;}for(int i = 0;i<array.size();i++){//!用剛剛那個有序的臨時數組，覆蓋原數組array[i] = tempArray[i];}vectorPrint(array);cout<<endl;}void radixSort(vector<int> &array){int maxNumIndex = 0;for(int i = 1;i<array.size();i++){ //!這里是找數組的最大值，確定計數排序的位數//!但是這里只考慮了數組內都是正整數的情況if(array[i]>array[maxNumIndex]){maxNumIndex = i;}}int max = array[maxNumIndex];for(int i = 1;i<=max;i = i*10){ //!按照個位，十位，百位。。。分別對數組進行計數排序countingSort(array,i);} }int main() {Tools::Time::AlgoTimeUs time1;Tools::Time::AlgoTimeUs time2;Tools::Time::AlgoTimeUs time3;vector<int> array;array = { 9, 6, 7, 5, 8, 8, 29, 15, 11, 10};vector<int> array2 = { 9, 6, 7, 5, 8, 8, 29, 15, 11, 10};vector<int> array3 = array2;cout<<"輸入數組："<<endl;vectorPrint(array);time1.start();cout << "計數排序基礎版" << endl;radixSort(array);cout << "算法用時：（微秒）";time1.printElapsed();cout << "排序結果：" << endl;vectorPrint(array);cout << ' ' << endl;return 0; }

總結

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

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