您可能感興趣的文章推薦 畫解順序表畫解鏈表畫解堆疊畫解佇列畫解哈希表畫解二叉樹畫解圖

目錄 零、演算法概述 一、插入排序 二、冒泡排序 三、選擇排序 四、計數排序 五、基數排序 六、歸并排序 七、快速排序 八、隨機快速 九、希爾排序 十、堆堆排序

??今天的內容，將圍繞這幾張動圖來展開，可以大致先簡單看一下，這是一個歸并排序的動圖演示，我會對以上幾個排序從演算法原理、動圖詳解講到 C語言的原始碼分析，

零、演算法概述 ??今天要講的內容是 「十大排序演算法」，各個排序演算法中的思想都非常經典，如果能夠一一消化，那么在學習演算法的路上也會輕松許多，

??相信看我文章的大多數都是「大學生」，能上大學的都是「精英」，那么我們自然要「精益求精」，如果你還是「大一」，那么太好了，你擁有大把時間，沒錯！利用這個時間 「學好演算法」，三年后的你自然「不能同日而語」，
??那么這里，我整理了「幾十個基礎演算法」 的分類，有需要可以找我領取，大致一覽：

🔥讓天下沒有難學的演算法🔥
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
入門級C語言真題匯總 🧡《C語言入門100例》🧡
幾張動圖學會一種資料結構 🌳《畫解資料結構》🌳
組團學習，抱團生長 🌌《演算法入門指引》🌌
競賽選手金典圖文教程 💜《夜深人靜寫演算法》💜

一、插入排序 ?? 「插入排序」 是比較好理解且編碼相對簡單的排序演算法，雖然效率不是很高，

一、🎯簡單釋義

1、演算法目的

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

2、演算法思想

??通過不斷將當前元素 「插入」 到 「升序」 序列中，直到所有元素都執行過 「插入」 操作，則演算法結束，

3、命名由來

??每次都是將元素 「插入」 到有序序列中，故此命名 「插入排序」 ，

二、🧡核心思想

「迭代」：類似的事情，不停地做，
「比較」：關系運算子小于等于( ≤ \le ≤) 的運用，
「移動」：原地后移元素，

三、🔆動圖演示

1、樣例


8	5	6	4	3	7	10	2

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

在這里插入圖片描述

圖二-1-1

2、演算法演示

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

圖二-2-1

3、樣例說明

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表正在執行比較和移動的數
■ 的柱形	代表已經排好序的數
■ 的柱形	代表待執行插入的數

??我們看到，首先需要將 「第二個元素」 和 「第一個元素」 進行 「比較」，如果前者小于等于后者，則將后者進行向后 「移動」，前者則執行插入；
??然后，進行第二輪「比較」，即 「第三個元素」 和 「第二個元素」、「第一個元素」 進行 「比較」，直到 「前三個元素」 保持有序，
??最后，經過一定輪次的「比較」 和 「移動」之后，一定可以保證所有元素都是 「升序」 排列的，

四、🌳演算法前置

1、回圈的實作

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

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

這個陳述句就是一個最簡單的回圈陳述句，它會將回圈體內的陳述句執行 n n n 次，而這里的 n n n 等于 1314 1314 1314，也就是會執行 1314 1314 1314 次，

2、比較的實作

「比較」兩個元素的大小，可以采用關系運算子，本文我們需要排序的陣列是按照 「升序」 排列的，所以用到的關系運算子是 「小于等于運算子（即 <=）」 ，
我們可以將兩個數的「比較」寫成一個函式smallerEqualThan，以 「 c++ 」 為例，實作如下：

#define Type int
bool smallerEqualThan(Type a, Type b) {
    return a <= b;
}

其中Type代表陣列元素的型別，可以是整數，也可以是浮點數，也可以是一個類的實體，這里我們統一用int來講解，即 32位有符號整型，

3、移動的實作

所謂「移動」，其實是將某個元素執行后移，實作如下：

a[j + 1] = a[j];

五、🥦演算法描述

1、問題描述

??給定一個 n n n 個元素的陣列，陣列下標從 0 0 0 開始，采用「插入排序」將陣列按照 「升序」排列，

2、演算法程序

整個演算法的執行程序分以下幾步：
??1）回圈迭代變數 i = 1 → n ? 1 i = 1 \to n-1 i=1→n?1；
??2）每次迭代，令 x = a [ i ] x = a[i] x=a[i]， j = i ? 1 j = i-1 j=i?1，回圈執行比較 x x x 和 a [ j ] a[j] a[j]，如果產生 x ≤ a [ j ] x \le a[j] x≤a[j] 則執行 a [ j + 1 ] = a [ j ] a[j+1] = a[j] a[j+1]=a[j]，然后執行 j = j + 1 j = j + 1 j=j+1，繼續執行 2）；否則，跳出回圈，回到 1），

六、🧶演算法分析

1、時間復雜度

我們假設 「比較」 和 「移動」 的時間復雜度為 O ( 1 ) O(1) O(1)，
「插入排序」 中有兩個嵌套回圈，

外回圈正好運行 n ? 1 n-1 n?1 次迭代，但內部回圈運行變得越來越短：
??當 i = 1 i = 1 i=1，內層回圈 1 1 1 次「比較」操作，
??當 i = 2 i = 2 i=2，內層回圈 2 2 2 次「比較」操作，
??當 i = 3 i = 3 i=3，內層回圈 3 3 3 次「比較」操作，
??……
??當 i = n ? 2 i = n-2 i=n?2，內層回圈 n ? 2 n-2 n?2 次「比較」操作，
??當 i = n ? 1 i = n-1 i=n?1，內層回圈 n ? 1 n-1 n?1 次「比較」操作，

因此，總「比較」次數如下：
1 + 2 + . . . + ( n ? 1 ) = n ( n ? 1 ) 2 1 + 2 + ... + (n-1) = \frac {n(n-1)}{2} 1+2+...+(n?1)=2n(n?1)?
總的時間復雜度為： O ( n 2 ) O(n^2) O(n2)

2、空間復雜度

由于演算法在執行程序中，只有「移動」變數時候，需要事先將變數存入臨時變數x，而其它沒有采用任何的額外空間，所以空間復雜度為 O ( 1 ) O(1) O(1)，

七、🧢優化方案

??「插入排序」在眾多排序演算法中效率較低，時間復雜度為 O ( n 2 ) O(n^2) O(n2) ，
?? 想象一下，當有 n = 1 0 5 n = 10^5 n=105 個數字，即使我們的計算機速度超快，并且可以在 1 秒內計算 1 0 8 10^8 108 次操作，但冒泡排序仍需要大約一百秒才能完成，
??考慮，在進行插入操作之前，我們找位置的程序是在有序陣列中找的，所以可以利用「二分查找」 來找到對應的位置，然而，執行 「插入」 的程序還是 O ( n ) O(n) O(n)，所以優化的也只是常數時間，最壞時間復雜度是不變的，

「改進思路」執行插入操作之前利用 「插入」 來找到需要插入的位置，

八、💙原始碼詳解

#include <stdio.h>

int a[1010];

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 InsertSort(int n, int *a) {       // (1)
    int i, j; 
    for(i = 1; i < n; ++i) {
        int x = a[i];                  // (2)
        for(j = i-1; j >= 0; --j) {    // (3)
            if(x <= a[j]) {            // (4)
                a[j+1] = a[j];         // (5)
            }else
                break;                 // (6)
        }
        a[j+1] = x;                    // (7)
    }
} 

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

( 1 ) (1) (1) void InsertSort(int n, int *a)為 插入排序 的實作，代表對a[]陣列進行升序排序，
( 2 ) (2) (2) 此時a[i]前面的 i-1個數都認為是排好序的，令x = a[i]；
( 3 ) (3) (3) 逆序的列舉所有的已經排好序的數；
( 4 ) (4) (4) 如果列舉到的數a[j]比需要插入的數x大，則當前數往后挪一個位置；
( 5 ) (5) (5) 執行挪位置的 O ( 1 ) O(1) O(1) 操作；
( 6 ) (6) (6) 否則，跳出回圈；
( 7 ) (7) (7) 將x插入到合適位置；

關于 「插入排序」 的內容到這里就結束了，

二、冒泡排序 ??想要養成 「演算法思維」，每一個簡單的問題都要思考它背后的真正含義，做到舉一反三，觸類旁通，
?? 「冒泡排序」 是最好理解且編碼最簡單的排序演算法，

一、🎯簡單釋義

1、演算法目的

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

2、演算法思想

??通過不斷比較相鄰的元素，如果「左邊的元素」 大于 「右邊的元素」，則進行「交換」，直到所有相鄰元素都保持升序，則演算法結束，

3、命名由來

??數值大的元素經過交換，不斷到達陣列的尾部，就像氣泡，逐漸浮出水面一樣，故此命名 「冒泡排序」 ，

二、🧡核心思想

「迭代」：類似的事情，不停地做，
「比較」：關系運算子大于( > \gt >) 的運用，
「交換」：變數或者物件的值的互換，

三、🔆動圖演示

1、樣例


8	5	6	4	3	7	10	2

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

圖二-1-1

2、演算法演示

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

圖二-2-1

3、樣例說明

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表正在執行比較的兩個數
■ 的柱形	代表已經排好序的數

??我們看到，首先需要將 「第一個元素」 和 「第二個元素」 進行 「比較」，如果前者大于后者，則進行 「交換」，然后再比較 「第二個元素」 和 「第三個元素」 ，以此類推，直到 「最大的那個元素」 被移動到 「最后的位置」 ，
??然后，進行第二輪「比較」，直到 「次大的那個元素」 被移動到 「倒數第二的位置」 ，
??最后，經過一定輪次的「比較」 和 「交換」之后，一定可以保證所有元素都是 「升序」 排列的，

四、🌳演算法前置

1、回圈的實作

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

int n = 520;
for(int i = 0; i < n; ++i) {
    // 回圈體
}

這個陳述句就是一個最簡單的回圈陳述句，它會將回圈體內的陳述句執行 n n n 次，而這里的 n n n 等于 520 520 520，也就是會執行 520 520 520 次，
具體的語法細節不是本文的主要內容，請自行學習，

2、比較的實作

「比較」兩個元素的大小，可以采用關系運算子，本文我們需要排序的陣列是按照 「升序」 排列的，所以用到的關系運算子是 「大于運算子（即 >）」 ，
我們可以將兩個數的「比較」寫成一個函式isBigger，以 「 c++ 」 為例，實作如下：

#define Type int
bool isBigger(Type a, Type b) {
    return a > b;
}

其中Type代表陣列元素的型別，可以是整數，也可以是浮點數，也可以是一個類的實體，這里我們統一用int來講解，即 32位有符號整型，

3、交換的實作

所謂「交換」，就是對于兩個變數，將它們的值進行互換，
在 「Python」 中，我們可以直接寫出下面這樣的代碼就實作了變數的交換，

a, b = b, a

在 「 c++ 」 里，這個語法是錯誤的，
我們可以這么理解，你有兩個杯子 a a a 和 b b b，兩個杯子里都盛滿了水，現在想把兩個杯子里的水「交換」一下，那么第一個想到的方法是什么？

當然是再找來一個臨時杯子：
??1）先把 a a a 杯子的水倒進這個臨時的杯子里；
??2）再把 b b b 杯子的水倒進 a a a 杯子里；
??3）最后把臨時杯子里的水倒進 b b b 杯子；

這種就是臨時變數法，以 「 c++ 」 為例，實作如下：

#define Type int
void swap(Type* a, Type* b) {
    Type tmp = *a;     // 把 a 杯子的水倒進臨時杯子
    *a = *b;           // 把 b 杯子的水倒進 a 杯子
    *b = tmp;          // 把 臨時杯子 的水 倒進 b 杯子
}

這里*涉及到的「指標」相關知識，屬于語法層面，請自行學習，

五、🥦演算法描述

1、問題描述

??給定一個 n n n 個元素的陣列，陣列下標從 0 0 0 開始，采用「冒泡排序」將陣列按照 「升序」排列，

2、演算法程序

整個演算法的執行程序分以下幾步：
??1）回圈迭代變數 i = 0 → n ? 1 i = 0 \to n-1 i=0→n?1；
??2）每次迭代，令 j = i j = i j=i，回圈執行比較 a [ j ] a[j] a[j] 和 a [ j + 1 ] a[j+1] a[j+1]，如果產生 a [ j ] > a [ j + 1 ] a[j] \gt a[j+1] a[j]>a[j+1] 則交換兩者的值，然后執行 j = j + 1 j = j + 1 j=j+1，這時候對 j j j 進行判斷，如果 j ≥ n ? 1 j \ge n-1 j≥n?1，則回到 1），否則繼續執行 2），

六、🧶演算法分析

1、時間復雜度

我們假設 「比較」 和 「交換」 的時間復雜度為 O ( 1 ) O(1) O(1)（為什么這里說假設，因為有可能要「比較」的兩個元素本身是陣列，并且是不定長的，所以只有當系統內置型別，我們才能說這兩個操作是 O ( 1 ) O(1) O(1) 的），
「冒泡排序」 中有兩個嵌套回圈，

外回圈正好運行 n ? 1 n-1 n?1 次迭代，但內部回圈運行變得越來越短：
??當 i = 0 i = 0 i=0，內層回圈 n ? 1 n-1 n?1 次「比較」操作，
??當 i = 1 i = 1 i=1，內層回圈 n ? 2 n-2 n?2 次「比較」操作，
??當 i = 2 i = 2 i=2，內層回圈 n ? 3 n-3 n?3 次「比較」操作，
??……
??當 i = n ? 2 i = n-2 i=n?2，內層回圈 1 1 1 次「比較」操作，
??當 i = n ? 1 i = n-1 i=n?1，內層回圈 0 0 0 次「比較」操作，

因此，總「比較」次數如下：
( n ? 1 ) + ( n ? 2 ) + . . . + 1 + 0 = n ( n ? 1 ) 2 (n-1) + (n-2) + ... + 1 + 0 = \frac {n(n-1)}{2} (n?1)+(n?2)+...+1+0=2n(n?1)?
總的時間復雜度為： O ( n 2 ) O(n^2) O(n2)

2、空間復雜度

由于演算法在執行程序中，只有「交換」變數時候采用了臨時變數的方式，而其它沒有采用任何的額外空間，所以空間復雜度為 O ( 1 ) O(1) O(1)，

七、🧢優化方案

??「冒泡排序」在眾多排序演算法中效率較低，時間復雜度為 O ( n 2 ) O(n^2) O(n2) ，
?? 想象一下，當有 n = 1 0 5 n = 10^5 n=105 個數字，即使我們的計算機速度超快，并且可以在 1 秒內計算 1 0 8 10^8 108 次操作，但冒泡排序仍需要大約一百秒才能完成，
??但是，它的外層回圈是可以提前終止的，例如，假設一開始所有數字都是升序的，那么在首輪「比較」的時候沒有發生任何的「交換」，那么后面也就不需要繼續進行 「比較」 了，直接跳出外層回圈，演算法提前終止，

「改進思路」如果我們通過內部回圈完全不交換，這意味著陣列已經排好序，我們可以在這個點上停止演算法，

八、💙原始碼詳解

#include <stdio.h>

int a[1010];

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 Swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void BubbleSort(int n, int *a) {             // (1)
    bool swapped;
    int last = n;
    do {
        swapped = false;                     // (2)
        for(int i = 0; i < last - 1; ++i) {  // (3)
            if(a[i] > a[i+1]) {              // (4)
                Swap(&a[i], &a[i+1]);        // (5)
                swapped = true;              // (6)
            }
        }
        --last;
    }while (swapped);
} 

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

( 1 ) (1) (1) void BubbleSort(int n, int *a)為冒泡排序的實作，代表對a[]陣列進行升序排序，
( 2 ) (2) (2) swapped標記本輪迭代下來，是否有元素產生了交換，
( 3 ) (3) (3) 每次冒泡的結果，會執行last的自減，所以待排序的元素會越來越少，
( 4 ) (4) (4) 如果發現兩個相鄰元素產生逆序，則將它們進行交換，保證右邊的元素一定不比左邊的小，
( 5 ) (5) (5) swap實作了元素的交換，這里需要用&轉換成地址作為傳參，
( 6 ) (6) (6) 標記更新，一旦標記更新，則代表進行了交換，所以下次迭代必須繼續，

關于 「冒泡排序」 的內容到這里就結束了，

三、選擇排序
?? 「選擇排序」 是比較直觀且編碼簡單的排序演算法，雖然效率不是很高，但一般也出現在各種 「資料結構」 的教科書上，

一、🎯簡單釋義

1、演算法目的

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

2、演算法思想

??通過不斷從未排序的元素中，「比較」 和 「交換」，從而 「選擇」 出一個最小的，直到最后變成一個「升序」 序列，則演算法結束，

3、命名由來

??每次都是「選擇」 出一個最小的元素，故此命名 「選擇排序」 ，

二、🧡核心思想

「迭代」：類似的事情，不停地做，
「比較」：關系運算子小于( < \lt <) 的運用，
「交換」：變數或者物件的值的互換，

三、🔆動圖演示

1、樣例


8	5	6	4	3	7	10	2

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

在這里插入圖片描述

圖二-1-1

2、演算法演示

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

圖二-2-1

3、樣例說明

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表正在執行比較的數
■ 的柱形	代表已經排好序的數
■ 的柱形	有兩種：1、記錄最小元素 2、執行交換的元素

??我們發現，首先從 「第一個元素」 到 「最后一個元素」 中選擇出一個 「最小的元素」，和 「第一個元素」 進行 「交換」；
??然后，從 「第二個元素」 到 「最后一個元素」 中選擇出一個 「最小的元素」，和 「第二個元素」 進行 「交換」，
??最后，一定可以保證所有元素都是 「升序」 排列的，

四、🌳演算法前置

1、回圈的實作

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

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

這個陳述句就是一個最簡單的回圈陳述句，它會將回圈體內的陳述句執行 n n n 次，而這里的 n n n 等于 5201314 5201314 5201314，也就是會執行 5201314 5201314 5201314 次，

2、比較的實作

「比較」兩個元素的大小，可以采用關系運算子，本文我們需要排序的陣列是按照 「升序」 排列的，所以用到的關系運算子是 「小于運算子（即 <）」 ，
我們可以將兩個數的「比較」寫成一個函式smallerThan，以 「 c++ 」 為例，實作如下：

#define Type int
bool smallerThan(Type a, Type b) {
    return a < b;
}

其中Type代表陣列元素的型別，可以是整數，也可以是浮點數，也可以是一個類的實體，這里我們統一用int來講解，即 32位有符號整型，

3、交換的實作

所謂「交換」，就是對于兩個變數，將它們的值進行互換，
在 「Python」 中，我們可以直接寫出下面這樣的代碼就實作了變數的交換，

a, b = b, a

在 「 c++ 」 里，這個語法是錯誤的，
我們可以這么理解，你有兩個杯子 a a a 和 b b b，兩個杯子里都盛滿了水，現在想把兩個杯子里的水「交換」一下，那么第一個想到的方法是什么？

當然是再找來一個臨時杯子：
??1）先把 a a a 杯子的水倒進這個臨時的杯子里；
??2）再把 b b b 杯子的水倒進 a a a 杯子里；
??3）最后把臨時杯子里的水倒進 b b b 杯子；

這種就是臨時變數法，以 「 c++ 」 為例，實作如下：

#define Type int
void swap(Type* a, Type* b) {
    Type tmp = *a;     // 把 a 杯子的水倒進臨時杯子
    *a = *b;           // 把 b 杯子的水倒進 a 杯子
    *b = tmp;          // 把 臨時杯子 的水 倒進 b 杯子
}

這里*涉及到的「指標」相關知識，屬于語法層面，請自行學習，

五、🥦演算法描述

1、問題描述

??給定一個 n n n 個元素的陣列，陣列下標從 0 0 0 開始，采用「選擇排序」將陣列按照 「升序」排列，

2、演算法程序

整個演算法的執行程序分以下幾步：
??1）回圈迭代變數 i = 0 → n ? 1 i = 0 \to n-1 i=0→n?1；
??2）每次迭代，令 m i n = i min = i min=i， j = i + 1 j = i+1 j=i+1；
??3）回圈執行比較 a [ j ] a[j] a[j] 和 a [ m i n ] a[min] a[min]，如果產生 a [ j ] < a [ m i n ] a[j] \lt a[min] a[j]<a[min] 則執行 m i n = j min = j min=j，執行 j = j + 1 j = j + 1 j=j+1，繼續執行這一步，直到 j = = n j == n j==n；
??4）交換 a [ i ] a[i] a[i] 和 a [ m i n ] a[min] a[min]，回到 1），

六、🧶演算法分析

1、時間復雜度

我們假設 「比較」 和 「交換」 的時間復雜度為 O ( 1 ) O(1) O(1)，
「選擇排序」 中有兩個嵌套回圈，

外回圈正好運行 n ? 1 n-1 n?1 次迭代，但內部回圈運行變得越來越短：
??當 i = 0 i = 0 i=0，內層回圈 n ? 1 n-1 n?1 次「比較」操作，
??當 i = 1 i = 1 i=1，內層回圈 n ? 2 n-2 n?2 次「比較」操作，
??當 i = 2 i = 2 i=2，內層回圈 n ? 3 n-3 n?3 次「比較」操作，
??……
??當 i = n ? 3 i = n-3 i=n?3，內層回圈 2 2 2 次「比較」操作，
??當 i = n ? 2 i = n-2 i=n?2，內層回圈 1 1 1 次「比較」操作，

因此，總「比較」次數如下：
( n ? 1 ) + . . . + 2 + 1 = n ( n ? 1 ) 2 (n-1) + ... + 2 + 1 = \frac {n(n-1)}{2} (n?1)+...+2+1=2n(n?1)?
總的時間復雜度為： O ( n 2 ) O(n^2) O(n2)

2、空間復雜度

由于演算法在執行程序中，只有「選擇最小元素」的時候，需要事先將最小元素的下標存入臨時變數min，而其它沒有采用任何的額外空間，所以空間復雜度為 O ( 1 ) O(1) O(1)，

七、🧢優化方案

??「選擇排序」在眾多排序演算法中效率較低，時間復雜度為 O ( n 2 ) O(n^2) O(n2) ，
?? 想象一下，當有 n = 1 0 5 n = 10^5 n=105 個數字，即使我們的計算機速度超快，并且可以在 1 秒內計算 1 0 8 10^8 108 次操作，但冒泡排序仍需要大約一百秒才能完成，
??考慮一下，每一個內層回圈是從一個區間中找到一個最小值，并且更新這個最小值，是一個「動態區間最值」問題，所以這一步，我們是可以通過「線段樹」 來優化的，這樣就能將內層回圈的時間復雜度優化成 O ( l o g 2 n ) O(log_2n) O(log2?n) 了，總的時間復雜度就變成了 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)，
??由于「線段樹」不是本文討論的重點，有興趣了解「線段樹」相關內容的讀者，可以參考以下這篇文章：夜深人靜寫演算法（三十九）- 線段樹，

八、💙原始碼詳解


#include <stdio.h>

int a[1010];

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 Swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void SelectionSort(int n, int *a) {  // (1)
    int i, j;
    for(i = 0; i < n - 1; ++i) {     // (2)
        int min = i;                 // (3)
        for(j = i+1; j < n; ++j) {   // (4)
            if(a[j] < a[min]) {
                min = j;             // (5)
            }
        }
        Swap(&a[i], &a[min]);        // (6) 
    }
}

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

( 1 ) (1) (1) void SelectionSort(int n, int *a)為選擇排序的實作，代表對a[]陣列進行升序排序，
( 2 ) (2) (2) 從首元素個元素開始進行 n ? 1 n-1 n?1 次跌迭代，
( 3 ) (3) (3) 首先，記錄min代表當前第 i i i 輪迭代的最小元素的下標為 i i i，
( 4 ) (4) (4) 然后，迭代列舉第 i + 1 i+1 i+1 個元素到最后的元素，
( 5 ) (5) (5) 選擇一個最小的元素，并且存盤下標到min中，
( 6 ) (6) (6) 將第 i i i 個元素和最小的元素進行交換，

關于 「選擇排序」 的內容到這里就結束了，

四、計數排序 ?? 「計數排序」 是比較好理解且編碼相對簡單的排序演算法，可以說是效率最高的排序演算法之一，但是也有 「局限性」，這個后面我會講，

一、🎯簡單釋義

1、演算法目的

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

2、演算法思想

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

3、命名由來

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

二、🧡核心思想

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

三、🔆動圖演示

1、樣例


2	3	1	3	2	1	4	2	4	6	2

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

圖二-1-1

2、演算法演示

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

圖二-2-1

3、樣例說明

圖示	含義
■ 的柱形	計數為 0 的數
■ 的柱形	計數為 1 的數
■ 的柱形	計數為 2 的數
■ 的柱形	計數為 3 的數
■ 的柱形	計數為 4 的數

??我們看到，首先程式生成了一個區間范圍為 [ 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 跳出回圈，

關于 「計數排序」 的內容到這里就結束了，

五、基數排序 ?? 「基數排序」 很好的彌補了 「計數排序」 中待排序的資料范圍過大的問題，它適合 「范圍大」 且 「數位少」 的整數的排序，它將所有的整數認為是一個字串，從最低有效位（最右邊的）到最高有效位（最左邊的）開始迭代，

一、🎯簡單釋義

1、演算法目的

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

2、演算法思想

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

二、🧡核心思想

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

三、🔆動圖演示

1、樣例


3121	897	3122	3	23	5	55	7	97	123	456	1327

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

圖二-1-1

2、演算法演示

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

圖二-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) 將佇列中的元素按順序塞回原陣列；

關于 「基數排序」 的內容到這里就結束了，

六、歸并排序 ?? 「歸并排序」 是利用了 「分而治之」 的思想，進行遞回計算的排序演算法，效率在眾多排序演算法中的佼佼者，一般也會出現在各種 「資料結構」 的教科書上，

一、🎯簡單釋義

1、演算法目的

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

2、演算法思想

??通過將當前亂序陣列分成長度近似的兩份，分別進行「遞回」 呼叫，然后再對這兩個排好序的陣列，利用兩個指標，將資料元素依次比較，選擇相對較小的元素存到一個「輔助陣列」中，再將「輔助陣列」中的資料存回「原陣列」，

3、命名由來

??每次都是將數列分成兩份，分別排序后再進行 「歸并」，故此命名 「歸并排序」 ，

二、🧡核心思想

「遞回」：函式通過改變引數，自己呼叫自己，
「比較」：關系運算子小于( < \lt <) 的運用，
「歸并」：兩個陣列合并成一個陣列的程序，

三、🔆動圖演示

1、樣例


8	5	6	4	3	7	10	2

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

在這里插入圖片描述

圖二-1-1

2、演算法演示

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

圖二-2-1

3、樣例說明

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表已經排好序的數
其他顏色 ■ 的柱形	正在遞回、歸并中的數

??我們發現，首先將 「 8個元素」 分成 「 4個元素」，再將 「 4個元素」 分成 「 2個元素」，然后 「比較」這「 2個元素」的值，使其在自己的原地陣列內有序，然后兩個 「 2個元素」 的陣列歸并變成 「 4個元素」 的 「升序」陣列，再將兩個「 4個元素」 的陣列歸并變成 「 8個元素」 的 「升序」陣列，

四、🌳演算法前置

1、遞回的實作

這個演算法本身需要做一些「遞回」計算，所以你至少需要知道「遞回」 的含義，這里以 「 C語言」 為例，來看下一個簡單的「遞回」是怎么寫的，代碼如下：

int sum(int n) {
    if(n <= 0) {
        return 0;
    } 
    return sum(n - 1) + n;
}

這就是一個經典的遞回函式，求的是從 1 1 1 到 n n n 的和，那么我們把它想象成 1 1 1 到 n ? 1 n-1 n?1 的和再加 n n n，而 1 1 1 到 n ? 1 n-1 n?1 的和為sum(n-1)，所以整個函式體就是兩者之和，這里sum(n)呼叫sum(n-1)的程序就被稱為「遞回」，

2、比較的實作

「比較」兩個元素的大小，可以采用關系運算子，本文我們需要排序的陣列是按照 「升序」 排列的，所以用到的關系運算子是 「小于運算子（即 <）」 ，
我們可以將兩個數的「比較」寫成一個函式smallerThan，以 「 C語言」 為例，實作如下：

#define Type int
bool smallerThan(Type a, Type b) {
    return a < b;
}

其中Type代表陣列元素的型別，可以是整數，也可以是浮點數，也可以是一個類的實體，這里我們統一用int來講解，即 32位有符號整型，

3、歸并的實作

所謂「歸并」，就是將兩個有序陣列合成一個有序陣列的程序，
如下圖所示：「紅色陣列」 和 「黃色陣列」 各自有序，然后通過一個額外的陣列，「歸并」 計算后得到一個有序的陣列，

在這里插入圖片描述

五、🥦演算法描述

1、問題描述

??給定一個 n n n 個元素的陣列，陣列下標從 0 0 0 開始，采用「歸并排序」將陣列按照 「升序」排列，

2、演算法程序

??整個演算法的執行程序用 mergeSort(a[], l, r)描述，代表當前待排序陣列 a a a，左區間下標 l l l，右區間下標 r r r，分以下幾步：
??1）計算中點 m i d = l + r 2 mid = \frac {l + r}{2} mid=2l+r?；
??2）遞回呼叫mergeSort(a[], l, mid)和mergeSort(a[], mid+1, r)；
??3）將 2）中兩個有序陣列進行有序合并，再存盤到a[l:r]；
??4）呼叫時，呼叫 mergeSort(a[], 0, n-1)就能得到整個陣列的排序結果，

??「遞回」是自頂向下的，實際上程式真正運行程序是自底向上「回溯」的程序：給定一個 n n n 個元素的陣列，「歸并排序」 將執行如下幾步：
??1）將每對單個元素歸并為 2個元素的有序陣列；
??2）將 2個元素的每對有序陣列歸并成 4個元素的有序陣列，重復這個程序…；
??3）最后一步：歸并 2 個 n / 2 n / 2 n/2 個元素的排序陣列（為了簡化討論，假設 n n n 是偶數）以獲得完全排序的 n n n 個元素陣列，

六、🧶演算法分析

1、時間復雜度

我們假設 「比較」 和 「賦值」 的時間復雜度為 O ( 1 ) O(1) O(1)，
我們首先討論「歸并排序」演算法的最重要的子程式： O ( n ) O(n) O(n) 歸并，然后決議這個歸并排序演算法，
給定兩個大小為 n 1 n_1 n1? 和 n 2 n_2 n2? 的排序陣列 A A A 和 B B B，我們可以在 O ( n ) O(n) O(n) 時間內將它們有效地歸并成一個大小為 n = n 1 + n 2 n = n_1 + n_2 n=n1?+n2? 的組合排序陣列，可以通過簡單地比較兩個陣列的前面并始終取兩個中較小的一個來實作的，
問題是這個歸并程序被呼叫了多少次？
由于每次都是對半切，所以整個歸并程序類似于一顆二叉樹的構建程序，次數就是二叉樹的高度，即 l o g 2 n log_2n log2?n，所以歸并排序的時間復雜度為 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)，

2、空間復雜度

由于歸并排序在歸并程序中需要額外的一個「輔助陣列」，并且最大長度為原陣列長度，所以「歸并排序」的空間復雜度為 O ( n ) O(n) O(n)，

七、🧢優化方案

??「歸并排序」在眾多排序演算法中效率較高，時間復雜度為 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) ，
?? 但是，由于歸并排序在歸并程序中需要額外的一個「輔助陣列」，所以申請「輔助陣列」記憶體空間帶來的時間消耗會比較大，比較好的做法是，實作用一個和給定元素個數一樣大的陣列，作為函式傳參傳進去，所有的 「輔助陣列」 干的事情，都可以在這個傳參進去的陣列上進行操作，這樣就免去了記憶體的頻繁申請和釋放，

八、💙原始碼詳解

#include <stdio.h>
#include <malloc.h>
 
#define maxn 1000001

int a[maxn];

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 MergeSort(int *nums, int l, int r) {
    int i, mid, p, lp, rp;
    int *tmp = (int *)malloc( (r-l+1) * sizeof(int) );    // (1)  
    if(l >= r) {
        return ;                                          // (2) 
    }
    mid = (l + r) >> 1;                                   // (3) 
    MergeSort(nums, l, mid);                              // (4) 
    MergeSort(nums, mid+1, r);                            // (5) 
    p = 0;                                                // (6) 
    lp = l, rp = mid+1;                                   // (7) 
    while(lp <= mid || rp <= r) {                         // (8) 
        if(lp > mid) {
            tmp[p++] = nums[rp++];                        // (9) 
        }else if(rp > r) {
            tmp[p++] = nums[lp++];                        // (10) 
        }else {
            if(nums[lp] <= nums[rp]) {                    // (11) 
                tmp[p++] = nums[lp++];
            }else {
                tmp[p++] = nums[rp++];
            }
        }
    }
    for(i = 0; i < r-l+1; ++i) {
        nums[l+i] = tmp[i];                               // (12) 
    } 
    free(tmp);                                            // (13) 
}

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

( 1 ) (1) (1) 申請一個輔助陣列，用于對原陣列進行歸并計算；
( 2 ) (2) (2) 只有一個元素，或者沒有元素的情況，則不需要排序；
( 3 ) (3) (3) 將陣列分為 [ l , m i d ] [l, mid] [l,mid] 和 [ m i d + 1 , r ] [mid+1, r] [mid+1,r] 兩部分；
( 4 ) (4) (4) 遞回排序 [ l , m i d ] [l, mid] [l,mid] 部分；
( 5 ) (5) (5) 遞回排序 [ m i d + 1 , r ] [mid+1, r] [mid+1,r] 部分；
( 6 ) (6) (6) 將需要排序的陣列快取到tmp中，用p作為游標；
( 7 ) (7) (7) 初始化兩個陣列的指標；
( 8 ) (8) (8) 當兩個指標都沒有到結尾，則繼續迭代；
( 9 ) (9) (9) 只剩下右邊的陣列，直接排；
( 10 ) (10) (10) 只剩下走右邊的陣列，直接排；
( 11 ) (11) (11) 取小的那個先進tmp陣列；
( 12 ) (12) (12) 別忘了將排序好的資料拷貝回原陣列；
( 13 ) (13) (13) 別忘了釋放臨時資料，否則就記憶體泄漏了！！！

關于 「歸并排序」 的內容到這里就結束了，

七、快速排序 ?? 「快速排序」 是利用了 「分而治之」 的思想，進行遞回計算的排序演算法，效率在眾多排序演算法中的佼佼者，

一、🎯簡單釋義

1、演算法目的

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

2、演算法思想

??隨機找到一個位置，將比它小的數都放到它 「左邊」，比它大的數都放到它「右邊」，然后分別「遞回」求解 「左邊」和「右邊」使得兩邊分別有序，

3、命名由來

??由于排序速度較快，故此命名 「快速排序」 ，

二、🧡核心思想

「遞回」：函式通過改變引數，自己呼叫自己，
「比較」：關系運算子小于( < \lt <) 的運用，
「分治」：意為分而治之，先分，再治，將問題拆分成兩個小問題，分別去解決，

三、🔆動圖演示

1、樣例


8	5	6	4	3	7	10	2

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

在這里插入圖片描述

圖二-1-1

2、演算法演示

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

圖二-2-1

3、樣例說明

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表隨機選定的基準數
■ 的柱形	代表已經排序好的數
■ 的柱形	代表正在遍歷比較的數
■ 的柱形	代表比基準數小的數
■ 的柱形	代表比基準數大的數

??我們發現，首先隨機選擇了一個 7 作為「基準數」，并且將它和最左邊的數交換，然后往后依次遍歷判斷，小于 7 的數為 「綠色」 ，大于 7 的數為「紫色」，遍歷完畢以后，將 7 和 「下標最大的那個比 7 小的數」交換位置，至此，7的左邊位置上的數都小于它，右邊位置上的數都大于它，左邊和右邊的數繼續遞回求解即可，

四、🌳演算法前置

1、遞回的實作

這個演算法本身需要做一些「遞回」計算，所以你至少需要知道「遞回」 的含義，這里以 「 C語言」 為例，來看下一個簡單的「遞回」是怎么寫的，代碼如下：

int sum(int n) {
    if(n <= 0) {
        return 0;
    } 
    return sum(n - 1) + n;
}

這就是一個經典的遞回函式，求的是從 1 1 1 到 n n n 的和，那么我們把它想象成 1 1 1 到 n ? 1 n-1 n?1 的和再加 n n n，而 1 1 1 到 n ? 1 n-1 n?1 的和為sum(n-1)，所以整個函式體就是兩者之和，這里sum(n)呼叫sum(n-1)的程序就被稱為「遞回」，

2、比較的實作

「比較」兩個元素的大小，可以采用關系運算子，本文我們需要排序的陣列是按照 「升序」 排列的，所以用到的關系運算子是 「小于運算子（即 <）」 ，
我們可以將兩個數的「比較」寫成一個函式smallerThan，以 「 C語言」 為例，實作如下：

#define Type int
bool smallerThan(Type a, Type b) {
    return a < b;
}

其中Type代表陣列元素的型別，可以是整數，也可以是浮點數，也可以是一個類的實體，這里我們統一用int來講解，即 32位有符號整型，

3、分治的實作

所謂「分治」，就是把一個復雜的問題分成兩個（或更多的相同或相似的）「子問題」，再把子問題分成更小的「子問題」……，直到最后子問題可以簡單的直接求解，原問題的解即「子問題」的解的合并，
對于 「快速排序」 來說，我們選擇一個基準數，將小于它的數都放到左邊，大于它的數都放到它的右邊，這個程序其實就是天然隔離了左邊的數和右邊的數，使得兩邊的數 “分開”，這樣就可以分開治理了，如下圖所示：

五、🥦演算法描述

1、問題描述

??給定一個 n n n 個元素的陣列，陣列下標從 0 0 0 開始，采用「快速排序」將陣列按照 「升序」排列，

2、演算法程序

??整個演算法的執行程序用 quickSort(a[], l, r)描述，代表當前待排序陣列 a a a，左區間下標 l l l，右區間下標 r r r，分以下幾步：
??1）隨機生成基準點 p i v o x = P a r t i t i o n ( l , r ) pivox = Partition(l, r) pivox=Partition(l,r)；
??2）遞回呼叫quickSort(a[], l, pivox - 1)和quickSort(a[], pivox +1, r)；
??3） Partition(l, r)回傳一個基準點，并且保證基準點左邊的數都比它小，右邊的數都比它大；Partition(l, r)稱為磁區，

六、🧶演算法分析

1、時間復雜度

首先，我們分析跑一次磁區的成本，
在實作磁區Partition(l, r)中，只有一個 for回圈遍歷 ( r ? l ) (r - l) (r?l) 次，由于 r r r 可以和 n ? 1 n-1 n?1 一樣大， i i i 可以低至 0 0 0，所以磁區的時間復雜度是 O ( n ) O(n) O(n)，
類似于歸并排序分析，快速排序的時間復雜度取決于磁區被呼叫的次數，
當陣列已經按照升序排列時，快速排序將達到最壞時間復雜度，總共 n n n 次磁區，磁區的時間計算如下： ( n ? 1 ) + . . . + 2 + 1 = n ( n ? 1 ) 2 (n-1) + ... + 2 + 1 = \frac {n(n-1)}{2} (n?1)+...+2+1=2n(n?1)?
總的時間復雜度為： O ( n 2 ) O(n^2) O(n2)
當磁區總是將陣列分成兩個相等的一半時，就會發生快速排序的最佳情況，如歸并排序，當發生這種情況時，遞回的深度只有 O ( l o g 2 n ) O(log_2n) O(log2?n)，總的時間復雜度為 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)，

2、空間復雜度

由于歸并排序在歸并程序中需要額外的一個「輔助陣列」，并且最大長度為原陣列長度，所以「歸并排序」的空間復雜度為 O ( n ) O(n) O(n)，

七、🧢優化方案

??「快速排序」在眾多排序演算法中效率較高，平均時間復雜度為 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)，但當完全有序時，最壞時間復雜度達到最壞情況 O ( n 2 ) O(n^2) O(n2)，
?? 所以每次在選擇基準數的時候，我們可以嘗試用隨機的方式選取，這就是 「隨機快速排序」，
??想象一下在隨機化版本的快速排序中，隨機化資料透視選擇，我們不會總是得到 0 0 0， 1 1 1 和 n ? 1 n-1 n?1 這種非常差的分割，所以不會出現上文提到的問題，

八、💙原始碼詳解

1、快速排序實作1

#include <stdio.h>
#include <malloc.h>
 
#define maxn 1000001

int a[maxn];

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 Swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int Partition(int a[], int l, int r){
    int i, j, pivox; 
    int idx = l + rand() % (r - l + 1);        // (1) 
    pivox = a[idx];                            // (2) 
    Swap(&a[l], &a[idx]);                      // (3) 
    i = j = l + 1;                             // (4) 
                                               // 
    while( i <= r ) {                          // (5) 
        if(a[i] < pivox) {                     // (6) 
            Swap(&a[i], &a[j]);                
            ++j;                               
        }
        ++i;                                   // (7) 
    }
    Swap(&a[l], &a[j-1]);                      // (8) 
    return j-1;
}


//遞回進行劃分
void QuickSort(int a[], int l, int r){
    if(l < r){
        int mid = Partition(a, l, r);
        QuickSort(a, l, mid-1);
        QuickSort(a, mid+1, r);
    }
}

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

( 1 ) (1) (1) 隨機選擇一個基準；
( 2 ) (2) (2) pivox 代表基準值；
( 3 ) (3) (3) 將基準和最左邊的值交換；
( 4 ) (4) (4) i i i 和 j j j 是兩個同步指標，都從 l + 1 l+1 l+1 開始； j ? 1 j-1 j?1 以后的數都是大于等于基準值的；
( 5 ) (5) (5) 開始遍歷整個排序區間， i i i 一定比 j j j 走的快，當 i i i 到達最右邊的位置時，遍歷結束；
( 6 ) (6) (6) 如果比基準值小的，交換 a [ i ] a[i] a[i] 和 a [ j ] a[j] a[j]，并且自增 j j j ；
( 7 ) (7) (7) 每次遍歷 i i i 都需要自增；
( 8 ) (8) (8) 第 j j j 個元素以后都是不比基準值小的元素；

2、快速排序實作2

#include <stdio.h>
#include <malloc.h>
 
#define maxn 1000001

int a[maxn];

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 Swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int Partition(int a[], int l, int r){
    int i, j; 
    int idx = l + rand() % (r - l + 1);        // (1) 
    Swap(&a[l], &a[idx]);                      // (2) 
    i = l, j = r;                              // (3) 
    int x = a[i];                              // (4) 
    while(i < j){
        while(i < j && a[j] > x)               // (5) 
            j--;
        if(i < j) 
             Swap(&a[i], &a[j]), ++i;          // (6) 
                                               // 
                                            
        while(i < j && a[i] < x)               // (7) 
            i++;
        if(i < j)
            Swap(&a[i], &a[j]), --j;           // (8) 
    }
    a[i] = x;
    return i;
}
//遞回進行劃分
void QuickSort(int a[], int l, int r){
    if(l < r){
        int mid = Partition(a, l, r);
        QuickSort(a, l, mid-1);
        QuickSort(a, mid+1, r);
    }
}

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

( 1 ) (1) (1) 隨機選擇一個基準；
( 2 ) (2) (2) 將基準和最左邊的值交換；
( 3 ) (3) (3) 初始區間 [ l , r ] [l, r] [l,r]；
( 4 ) (4) (4) 這里的 x x x 是一開始隨機出來那個基準值；
( 5 ) (5) (5) 從右往左找，第一個滿足a[j] <= x基準值的，退出回圈；
( 6 ) (6) (6) 如果a[j] <= x基準值，則a[j]必須和 x交換，才能滿足a[j]在基準值左邊；且此時基準值是a[i]，交換完，基準值變成原先的a[j]，且 i i i 需要自增一次；
( 7 ) (7) (7) 從左往右找，第一個滿足a[i] >= x基準值的，退出回圈；
( 8 ) (8) (8) 如果a[i] >= x，則a[i]必須和x交換，才能滿足a[i]在基準值右邊；交換完，基準值又變回為a[i]，繼續迭代；

關于 「快速排序」 的內容到這里就結束了，

八、隨機快速 ?? 「隨機快速排序」 在上文已經有所介紹，即基準數的選擇采用隨機的方式進行，

九、希爾排序 ??文章較長，導致編輯卡頓，故后續將在如下鏈接更新， 《畫解資料結構》（4 - 8）- 希爾排序

十、堆堆排序 ??文章較長，導致編輯卡頓，故后續將整理至在如下鏈接更新， 《畫解資料結構》（2 - 3）- 堆與優先佇列

如果還有不懂的問題，可以通過 「作者主頁」找到作者的「聯系方式」 進行在線咨詢，
有關🌳《畫解資料結構》🌳 的原始碼均開源，鏈接如下：《畫解資料結構》

🔥讓天下沒有難學的演算法🔥
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
入門級C語言真題匯總 🧡《C語言入門100例》🧡
幾張動圖學會一種資料結構 🌳《畫解資料結構》🌳
組團學習，抱團生長 🌌《演算法入門指引》🌌
競賽選手金典圖文教程 💜《夜深人靜寫演算法》💜

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296586.html

標籤：其他

上一篇：python每日演算法 | 圖文挑戰十大排序演算法DAY1，再也不用擔心面試官問冒泡、選擇、插入排序！持續更新，收藏起來?

下一篇：面試官：如果你訪問一個網站很慢，怎么排查和解決？

??五萬字《十大排序演算法》動圖講解??(建議收藏)

一、🎯簡單釋義

二、🧡核心思想

三、🔆動圖演示

四、🌳演算法前置

五、🥦演算法描述

六、🧶演算法分析

七、🧢優化方案

八、💙原始碼詳解

一、🎯簡單釋義

二、🧡核心思想

三、🔆動圖演示

四、🌳演算法前置

五、🥦演算法描述

六、🧶演算法分析

七、🧢優化方案

八、💙原始碼詳解

一、🎯簡單釋義

二、🧡核心思想

三、🔆動圖演示

四、🌳演算法前置

五、🥦演算法描述

六、🧶演算法分析

七、🧢優化方案

八、💙原始碼詳解

一、🎯簡單釋義

二、🧡核心思想

三、🔆動圖演示

四、🌳演算法前置

五、🥦演算法描述

六、🧶演算法分析

七、🧢優化方案

八、💙原始碼詳解

一、🎯簡單釋義

二、🧡核心思想

三、🔆動圖演示

四、🌳演算法前置

五、🥦演算法描述

六、🧶演算法分析

七、🧢優化方案

八、💙原始碼詳解

一、🎯簡單釋義

二、🧡核心思想

三、🔆動圖演示

四、🌳演算法前置

五、🥦演算法描述

六、🧶演算法分析

七、🧢優化方案

八、💙原始碼詳解

一、🎯簡單釋義

二、🧡核心思想

三、🔆動圖演示

四、🌳演算法前置

五、🥦演算法描述

六、🧶演算法分析

七、🧢優化方案

八、💙原始碼詳解