• 本文已收錄于專欄《資料結構入門》

零、📃前言

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

??「 計數排序 」 是比較好理解且編碼相對簡單的排序演算法，可以說是效率最高的排序演算法之一，但是也有「 局限性 」，這個后面我會講，在講排序這塊內容時，我會盡量做到「 深入淺出 」，讓 90% 的 「 零基礎小白 」 也都能理解，真正做到 「讓天下沒有難學的演算法」 ，我知道這很難，但是我愿意嘗試！我會盡量把文章寫得有趣，一氣呵成，不浪費讀者的寶貴時間，畢竟，「 時間就是金錢 」，

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

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

一、🎯簡單釋義

1、演算法目的

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

2、演算法思想

??首先，準備一個 「 計數器陣列 」，通過一次 「 列舉 」，對所有「 原陣列 」元素進行計數，
??然后，「 從小到大 」列舉所有數，按照 「 計數器陣列 」 內的個數，將列舉到的數放回 「 原陣列 」，執行完畢以后，所有元素必定按照 「升序」 排列，

3、命名由來

??整個程序的核心，就是在 「計算某個數的數量」，故此命名 「 計數排序 」 ，

二、🧡核心思想

• 「列舉」：窮舉所有情況，
• 「哈希」：將一個數字映射到一個陣列中，
• 「計數」：一次計數就是一次自增操作，

三、🔆動圖演示

1、樣例

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

2、演算法演示

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

3、樣例說明

??我們看到，首先程式生成了一個區間范圍為 [ 1 , 9 ] [1, 9] [1,9] 的 「 計數器陣列 」，并且一開始所有值的計數都為 0，
??然后，遍歷列舉「 原陣列 」的所有元素，在 元素值 對應的計數器上執行 「 計數 」 操作，
??最后，遍歷列舉「 計數器陣列 」，按照陣列中元素個數放回到 「 原陣列 」 中，這樣，一定可以保證所有元素都是 「升序」 排列的，

四、🌳演算法前置

1、回圈的實作

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

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

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

2、哈希的實作

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

cnt[5] = 1;

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

3、計數的實作

• 「 計數 」 就比較簡單了，直接對「 哈希 」的位置執行自增操作即可，如下：

++cnt[5];

五、🥦演算法描述

1、問題描述

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

2、演算法程序

整個演算法的執行程序分以下幾步：
??1） 初始化計數器陣列cnt[i] = 0，其中 i ∈ [ 1 , 1 0 5 ] i \in [1, 10^5] i∈[1,105]；
??2） 令 i = 0 → n ? 1 i = 0 \to n-1 i=0→n?1，回圈執行計數器陣列的自增操作 ++cnt[a[i]]；
??3） 令 i = 1 → 100000 i = 1 \to 100000 i=1→100000，檢測cnt[i]的值，如果非零，則將cnt[i]個i的值依次放入原陣列a[]中，

六、🧶演算法分析

1、時間復雜度

• 我們假設一次 「 哈希 」 和 「 計數 」 的時間復雜度均為 O ( 1 ) O(1) O(1)，并且總共 n n n 個數，數字范圍為 1 → k 1 \to k 1→k，

除了輸入輸出以外，「 計數排序 」 中總共有四個回圈，
?? 第一個回圈，用于初始化 「 計數器陣列 」，時間復雜度 O ( k ) O(k) O(k)；
?? 第二個回圈，列舉所有數字，執行「 哈希 」 和 「 計數 」 操作，時間復雜度 O ( n ) O(n) O(n)；
?? 第三個回圈，列舉所有范圍內的數字，時間復雜度 O ( k ) O(k) O(k)；
??第四個回圈，是嵌套在第三個回圈內的，最多走 O ( n ) O(n) O(n)，雖然是嵌套，但是它可第三個回圈是相加的關系，而并非相乘的關系，

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

2、空間復雜度

• 假設最大的數字為 k k k，則空間復雜度為 O ( k ) O(k) O(k)，

七、🧢優化方案

??「 計數排序 」在眾多排序演算法中效率最高，時間復雜度為 O ( n + k ) O(n + k) O(n+k) ，
?? 但是，它的缺陷就是非常依賴它的資料范圍，必須為整數，且限定在 [ 1 , k ] [1, k] [1,k] 范圍內，所以由于記憶體限制， k k k 就不能過大，優化點都是常數優化了，主要有兩個：
??(1) 初始化 「 計數器陣列 」 可以采用系統函式memset，純記憶體操作，由于回圈；
??(2) 上文提到的第三個回圈，當排序元素達到 n n n 個時，可以提前結束，跳出回圈，

八、💙原始碼詳解

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

#define maxn 1000001
#define maxk 100001

int a[maxn];
int cnt[maxk]; 

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

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

void CountingSort(int n, int *a) {       // (1)
    int i, top; 
    memset(cnt, 0, sizeof(cnt));         // (2) 
    for(i = 0; i < n; ++i) {             // (3)
        ++cnt[ a[i] ];                   // (4)
    }
    top = 0;                             // (5)
    for(i = 0; i < maxk; ++i) {
        while(cnt[i]) {                  // (6)
            a[top++] = i;                // (7)
            --cnt[i];                    // (8)
        }
        if(top == n) {                   // (9)
            break;
        }
    }
} 

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        Input(n, a);
        CountingSort(n, a);
        Output(n, a);
    }
    return 0;
} 

• ( 1 ) (1) (1) void CountingSort(int n, int *a)為 計數排序 的實作，代表對a[]陣列進行升序排序，
• ( 2 ) (2) (2) 利用memset初始化 計數器陣列 cnt；
• ( 3 ) (3) (3) 遍歷原陣列中的每個元素；
• ( 4 ) (4) (4) 相應數 的 計數器 增加1；
• ( 5 ) (5) (5) 堆疊頂指標指向空堆疊；
• ( 6 ) (6) (6) 如果 i i i 這個數的計數 c n t [ i ] cnt[i] cnt[i] 為零，則結束回圈，否則進入 ( 7 ) (7) (7)；
• ( 7 ) (7) (7) 將 i i i 放入原陣列；
• ( 8 ) (8) (8) 計數器減一；
• ( 9 ) (9) (9) 當原陣列個數 等于 n n n 跳出回圈，

九、💗代碼驗證

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

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