零、📃前言

??這個系列的文章中，我會著重講解一些常見的 「 演算法和資料結構 」 的設計思想，并且配上動圖，希望讀者能夠帶上自己的 「思考」，主要針對面試中常見的問題和新手朋友們比較難理解的點進行決議，當然，這個系列的文章，后面也會給出面向演算法競賽的提綱，如果有興趣深入學習的歡迎在「評論區留言，一起成長交流」 ，
??零基礎學演算法的最好方法，莫過于刷題了，當然，刷題是不夠的，刷的程序中也要多多總結，多多思考，養成 「經常思考」 的習慣，這就是所謂的 「 流水不腐，戶樞不蠹 」，任何事情都是需要堅持的，刷題也一樣，沒有刷夠足夠的題，就很難做出系統性的總結，所以上大學的時候，我花了三年的時間來刷題， 作業以后還是會抽點時間出來刷題，
??千萬不要用作業忙來找借口，時間擠一擠總是有的，當然，每天不需要花太多時間在這個上面，把這個事情做成一個規劃，按照長期去推進，反正也沒有 KPI 壓力，就當成是作業之余的一種消遣，還能夠提升思維能力，
??所以，無論你是 小學生，中學生，高中OIer，大學ACMer，職場人士，只要想開始，一切都不會太晚！
??今天要講的主要內容是：「 基數排序 」，希望讀者朋友給個面子，幫我完成閱讀，不能完讀，我可就完犢子了 🤣，當然，如果你覺得還可以，給我個「 贊 」 和 「 收藏 」，這個對我很重要，謝謝了！
??「 基數排序 」 很好的彌補了 「 計數排序 」 中待排序的資料范圍過大的問題，它適合 「 范圍大 」 且 「 數位少 」 的整數的排序，它將所有的整數認為是一個字串，從最低有效位（最右邊的）到 最高有效位（最左邊的）開始迭代，我會盡量做到「 深入淺出 」，讓 90% 的 「 零基礎小白 」 也都能理解，真正做到 「讓天下沒有難學的演算法」 ，我知道這很難，但是我愿意嘗試！我會盡量把文章寫得有趣，一氣呵成，不浪費讀者的寶貴時間，畢竟，「 時間就是金錢 」，那么，接下來，讓我們開始今天的主題：

「 基數排序 」

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《畫解資料結構》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌

那么，我的教程和別人的教程有什么不同的地方呢？
??「第一步」簡單釋義： 我會簡單解釋一下這個演算法的目的、思想、以及為什么叫這個名字以幫助記憶，
??「第二步」核心思想： 我會大致介紹一下這個演算法的核心思想，
??「第三步」動圖演示： 我會引入一個動圖，并且用一個切實的例子展示一下演算法執行的全程序，
??「第四步」演算法前置： 在學習這個演算法之前，我們需要學習的前置內容有哪些？這些內容是需要事先去攻克的，
??「第五步」演算法描述： 細致的講解整個演算法的執行流程，
??「第六步」演算法分析： 對演算法的時間復雜度和空間復雜度進行一個詳細的分析，
??「第七步」優化方案： 介紹一些可以優化的點，
??「第八步」代碼實踐： 用 C/C++ 來實作上述演算法，
??「第九步」代碼驗證： 最后，我會推薦一些比較好用的在線評測系統來驗證我們實作的演算法的正確性，

一、🎯簡單釋義

1、演算法目的

??將原本亂序的陣列變成有序，可以是 「升序」 或者 「降序」 （為了描述統一，本文一律只討論 「 升序」 的情況），

2、演算法思想

??首先，準備 10 個佇列，進行若干次「 迭代 」，每次「 迭代 」，先清空佇列，然后取每個待排序數的對應十進制位，通過「 哈希 」，映射到它「 對應的佇列 」中，然后將所有數字「 按照佇列順序 」塞回「 原陣列 」完成一次「 迭代 」，
??可以認為類似「 關鍵字排序 」，先對「 第一關鍵字 」進行排序，再對「 第二關鍵字 」排序，以此類推，直到所有關鍵字都有序為止，

二、🧡核心思想

• 「迭代」：類似的事情，不停地做，
• 「哈希」：將一個數字映射到一個陣列中，
• 「佇列」：一種「 先進先出 」的資料結構，

三、🔆動圖演示

1、樣例

• 初始情況下的資料如 圖二-1-1 所示，基本屬于亂序，純隨機出來的資料，

2、演算法演示

• 接下來，我們來看下排序程序的影片演示，如 圖二-2-1 所示：

3、樣例說明

• 上圖中 「 紅色的數字位 」 代表需要進行 「 哈希 」 映射到給定 「 佇列 」 中的數字位，

??我們看到，首先程式生成了一個區間范圍為 [ 0 , 9 ] [0, 9] [0,9] 的 「 基數佇列 」，
??然后，總共進行了 4 輪「 迭代 」（因為最大的數總共 4 個數位），
??每次迭代，遍歷列舉 「 原陣列 」 中的所有數，并且取得本次迭代對應位的數字，通過「 哈希 」，映射到它「 對應的佇列 」中 ，然后將 「 佇列 」 中的資料按順序塞回 「 原陣列 」 完成一次「 迭代 」，4 次「 迭代 」后，一定可以保證所有元素都是 「升序」 排列的，

四、🌳演算法前置

1、回圈的實作

• 這個演算法本身需要做一些「 回圈 」進行列舉計算，所以你至少需要知道「 回圈 」 的含義，這里以 「 c++ 」 為例，來看下一個簡單的「 回圈 」是怎么寫的，代碼如下：

int n = 128;
for(int i = 0; i < n; ++i) {
    // TODO ： ，，，
}

• 這個陳述句就是一個最簡單的回圈陳述句，它會將回圈體內的陳述句執行 n n n 次，而這里的 n n n 等于 128 128 128，也就是會執行 128 128 128 次，
• 「 回圈 」 是計算機完成 「 列舉 」 和 「 迭代 」 的基礎操作，

2、哈希的實作

• 「 哈希 」就是將一個數字「 映射 」到一個「 陣列 」中，然后通過陣列的 「 取下標 」 這一步來完成 O ( 1 ) O(1) O(1) 的 「 查詢 」 操作 ，
• 所有 「 計數排序 」 對待排序陣列中的元素，是有范圍要求的，它的值不能超過陣列本身的大小，這就是上文提到的 「 局限性 」，
• 如下代碼所示，代表的是把 數字5 「 哈希 」到cnt陣列的第 6（C語言中下標從 0 開始） 個槽位中，并且將值置為 1，

cnt[5] = 1;

• 有關「 哈希 」的更多內容，可以參考：夜深人靜寫演算法（九）- 哈希表，

3、佇列的實作

• 佇列是一種 「 先進先出 」 的資料結構，本文會采用數字來實作，下文會有講到，如果有興趣了解更多內容，可以參考這篇文章：詳解佇列，

4、十進制位數計算

• 在進行排序程序中，我們需要取得一個數字 v v v 的十進制的第 k k k 位的值，如下
• v = a p 1 0 p + a p ? 1 1 0 p ? 1 . . . + a k 1 0 k + . . . + a 1 1 0 1 + a 0 1 0 0 v = a_p10^p + a_{p-1}10^{p-1}... + a_k10^k + ... + a_110^1 + a_010^0 v=ap?10p+ap?1?10p?1...+ak?10k+...+a1?101+a0?100
• 我們要得到的就是 a k a_k ak?，
• 可以將 v v v 直接除上 1 0 k 10^k 10k 再模上 10，即 v 1 0 k m o d 10 \frac v {10^k} \ mod \ 10 10kv? mod 10，
• 正確性顯而易見，比 1 0 k 10^k 10k 高的位，除完 1 0 k 10^k 10k 以后必然是 10 10 10 的倍數，所以模 10 10 10 以后答案為 0 0 0，不會產生貢獻；比 1 0 k 10^k 10k 低的位，除完 1 0 k 10^k 10k 以后本身就已經變成了 0 0 0，更加不會產生貢獻，所以剩下的只有 1 0 k 10^k 10k 的系數，即 a k a_k ak?，

五、🥦演算法描述

1、問題描述

??給定一個 n n n 個元素的整型陣列，陣列下標從 0 0 0 開始，且陣列元素范圍為 [ 1 , 1 0 8 ) [1, 10^8) [1,108)，采用「 基數排序 」將陣列按照 「升序」排列，

2、演算法程序

整個演算法的執行程序分以下幾步：
??1） 定好進制，一般為 10 10 10，然后預處理 10 10 10 的冪，存盤在陣列中，PowOfBase[i]代表 1 0 i 10^i 10i；
??2） 由于資料范圍為 [ 1 , 99999999 ] [1, 99999999] [1,99999999]，即 8 8 8 個 9 9 9，最多 8 8 8 位，所以可以令 p o s = 0 → 7 pos = 0 \to 7 pos=0→7，執行下一步；
??3） 初始化 [ 0 , 9 ] [0,9] [0,9] 佇列，對 n n n 個數字取 p o s pos pos 位，放入對應的佇列中；
??4） 從第 0 0 0 個佇列到 第 9 9 9 個佇列，將所有數字按照順序取出來，放回原陣列，然后 p o s = p o s + 1 pos = pos + 1 pos=pos+1，回到 3） 繼續迭代；

六、🧶演算法分析

1、時間復雜度

• 我們假設一次 「 哈希 」 以及 「 入隊 」、「 出隊 」 的時間復雜度均為 O ( 1 ) O(1) O(1)，并且總共 n n n 個數，數字位數為 1 → k 1 \to k 1→k，

除了輸入輸出以外，「 基數排序 」 中總共有 k k k 輪 「 迭代 」，
?? 每一輪「 迭代 」，都需要遍歷陣列中的所有數，進行 「 入隊 」 操作，時間復雜度 O ( n ) O(n) O(n)，所有數都 「 入隊 」 完畢以后，需要將所有佇列中的數塞回 「 原陣列 」 ，時間復雜度也是 O ( n ) O(n) O(n)，

• 所以，總的時間復雜度為： O ( n k ) O(nk) O(nk)

2、空間復雜度

• 空間復雜度需要看 「 佇列 」 的實作方式，如果采用靜態陣列，那么總共的佇列個數為 b b b 個（這里 b = 10 b = 10 b=10），每個佇列最多元素為 n n n，則空間復雜度為 O ( n b ) O(nb) O(nb)，牛逼啊！
• 如果利用 S T L STL STL 的佇列動態分配記憶體，則可以達到 O ( n ) O(n) O(n) ，

七、🧢優化方案

??「 基數排序 」 的時間復雜度為 O ( n k ) O(nk) O(nk) ，
?? 其中 k k k 代表數字位的個數，所以比較依賴資料，如果最大的那個數的位數小，某次迭代下來，所有的數都已經放在一個佇列中了，那就沒必要繼續迭代了，這里可以進行一波常數優化，

八、💙原始碼詳解

#include <stdio.h>
#include <string.h>

const int MAXN = 100005;          // (1) 
const int MAXT = 8;               // (2) 
const int BASE = 10;              // (3) 
int PowOfBase[MAXT];              // (4) 
int RadixBucket[BASE][MAXN];      // (5) 
int RadixBucketTop[BASE];         // (6) 


void InitPowOfBase() {
    int i;
    PowOfBase[0] = 1;
    for(i = 1; i < MAXT; ++i) {
        PowOfBase[i] = PowOfBase[i-1] * BASE;   // (7)
    }
}

void Input(int n, int *a) {
    int i;
    for(i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void Output(int n, int *a) {
    int i; 
    for(i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

int getRadix(int value, int pos) {
    return value / PowOfBase[pos] % BASE;        // (8)
}

void RadixSort(int n, int *a) {                  // (9)
    int i, j, top = 0, pos = 0;
    while (pos < MAXT) {                         // (10)
        memset(RadixBucketTop, 0, sizeof(RadixBucketTop));      // (11)
        for(i = 0; i < n; ++i) {
            int rdx = getRadix(a[i], pos);
            RadixBucket[ rdx ][ RadixBucketTop[rdx]++ ] = a[i]; // (12)
        }
        top = 0;
        for(i = 0; i < BASE; ++i) {
            for(j = 0; j < RadixBucketTop[i]; ++j) {
                a[top++] = RadixBucket[i][j];                   // (13)
            }
        }
        ++pos; 
    }
}

int a[MAXN];

int main() {
    int n;
    InitPowOfBase();
    while(scanf("%d", &n) != EOF) {
        Input(n, a);
        RadixSort(n, a);
        Output(n, a);
    }
    return 0;
} 
/*
15
3221 1 10 9680 577 9420 7 5622 4793 2030 3138 82 2599 743 4127
*/

• ( 1 ) (1) (1) 排序陣列的元素最大個數；
• ( 2 ) (2) (2) 排序元素的數字的最大位數；
• ( 3 ) (3) (3) 排序元素的進制，這里為 十進制；
• ( 4 ) (4) (4) PowOfBase[i]代表BASE的i次冪；
• ( 5 ) (5) (5) RadixBucket[i][]代表第 i i i 個佇列；
• ( 6 ) (6) (6) RadixBucketTop[i]代表第 i i i 個佇列的尾指標；
• ( 7 ) (7) (7) 初始化BASE的i次冪；
• ( 8 ) (8) (8) 計算value的pos位的值；
• ( 9 ) (9) (9) void RadixSort(int n, int *a)為 基數排序 的實作，代表對a[]陣列進行升序排序；
• ( 10 ) (10) (10) 進行MAXT輪迭代；
• ( 11 ) (11) (11) 迭代前清空佇列，只需要將佇列尾指標置零即可；
• ( 12 ) (12) (12) 入隊操作；
• ( 13 ) (13) (13) 將佇列中的元素按順序塞回原陣列；

九、💗代碼驗證

• 比如，你可以在百度上搜索 代碼在線提交、OnlineJudge、LeetCode、洛谷、HDOJ、POJ 等等的關鍵詞，然后去找對應的題目提交驗證你的代碼的正確性，

• 關于 「 基數排序 」 的內容到這里就結束了，
• 如果還有不懂的問題，可以 「 想方設法 」找到作者的「 聯系方式 」 進行在線咨詢，

• 有關🌳《畫解資料結構》🌳 的原始碼均開源，鏈接如下：《畫解資料結構》

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《畫解資料結構》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌