基數排序不同前面的各種排序，它并不基于比較排序，而是采用多關鍵字排序。通常，按照低位至高位的順序進行排序的，也就是最低位優先（LSD）。

本文也是采用最低位優先排序，代碼是對簡單的兩位數進行基數排序，所采用的存儲結構為二維數組，僅為說明基數排序的思想。在此基礎上便可以進行多位數的排序，也可以采用鏈表進行存儲，都是可以的。

計數排序過程可粗略的看為 分配-收集，分配-收集，.....，以最低位優先為例，第一次分配是按照數列的個位數分配到給定的存儲結構中，分配好所有數之后，按順序從存儲結構一個個收集；第二次分配是按照數列的十位數進行分配，然后收集；再分配百位數，再收集......如對數列? 7 10 46 31 29 30進行基數排序：

第一趟分配結果為（10，30），（31），（46），（7），（29）

第一趟收集結果為? 10 30 31 46 7 29

第二趟分配結果為（7），（10），（29），（30，31），（46）

第二趟收集結果為? 7 10 29 30 31 46 ? ?? 排序結束。

注：存儲結構中應該是按照基數0~9排列的，而數列沒有個位是2的數，如第一趟分配結果完整描述為：

（10，30），（31），（），（），（），（），（46），（7），（），（29）

基數排序的時間復雜度為 d趟分配和收集所需的時間，一趟分配的時間為o(n),一趟收集的時間最大為o(n+r)，r為基數，本文中r為10。故其時間復雜度最大為o(d*(2n+r))； 空間復雜度最大為o(n+r)；基數排序是穩定的。

完整代碼如下：

#include<iostream> #include<cstring> #define N 20 void baseSort(int* arr, int num); int back[10][10];//存儲空間 int main() {int a[N] = { 3, 2, 4, 6, 7, 5, 18, 9, 10, 1,16, 8, 20, 33, 28, 64, 19, 31, 30, 25 };for (int i = 0; i < N; i++){std::cout << a[i] << " ";}std::cout << '\n';baseSort(a, N);for (int i = 0; i < N; i++){std::cout << a[i] << " ";}std::cout << '\n';return 0; }void baseSort(int* arr, int num) {int i, j, temp; for (i = 0; i < num; i++)//按個位分配{j = 0;temp = arr[i] % 10;while (back[temp][j] != 0)++j;back[temp][j] = arr[i];}j = 0;for (i = 0; i < 10; i++)//回收{temp = 0;while(back[i][temp] != 0)arr[j++] = back[i][temp++];}memset(back, 0, 400);//二維數組清零for (i = 0; i < num; i++)//按十位分配{j = 0;temp = arr[i] / 10;while (back[temp][j] != 0)++j;back[temp][j] = arr[i];}j = 0;for (i = 0; i < 10; i++)//回收{temp = 0;while (back[i][temp] != 0)arr[j++] = back[i][temp++];} }

?

總結

以上是生活随笔為你收集整理的基数排序（c/c++）的全部內容，希望文章能夠幫你解決所遇到的問題。

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