排序算法整理(冒泡排序，選擇排序，直接插入排序，希爾排序，快速排序，堆排序，歸并排序)

排序算法

​ 排序即将一個資料元素的任意序列，重新排列稱一個按關鍵字有序的序列。

​ 根據在排序過程中排序的記錄是否全部被放置在記憶體中，排序分為兩種，内部排序和外部排序。

1. 内部排序：在排序期間資料對象全部存放在記憶體的排序
2. 外部排序：在排序期間全部對象個數太多，不能同時存放在記憶體，必須根據排序過程的要求，不斷在記憶體和外存之間移動的排序。

對于排序來說，隻有兩個最基本的操作，第一個就是比較，比較不同資料之間的關鍵字的大小關系；第二個就是移動，在得到比較結果之後，按照一定的規則來移動元素使其最終有序。

文章目錄

• 排序算法
• • 排序算法性能衡量
  • 冒泡排序
  • • 冒泡排序-算法原理
    • 冒泡排序-算法實作
    • 冒泡排序-性能分析
  • 選擇排序
  • • 選擇排序-算法原理
    • 選擇排序-算法實作
    • 選擇排序-性能分析
  • 直接插入排序
  • • 直接插入排序-算法原理
    • 直接插入排序-算法實作
    • 直接插入排序-性能分析
  • 希爾排序
  • • 希爾排序-算法原理
    • 希爾排序-算法實作
    • 希爾排序-性能分析
  • 快速排序
  • • 快速排序-算法原理
    • 快速排序-算法實作
    • 快速排序-性能分析
  • 堆排序
  • • 堆排序-算法原理
    • 堆排序-算法實作
    • 堆排序-性能分析
  • 歸并排序
  • • 歸并排序-算法原理
    • 歸并排序-算法實作
    • 歸并排序-性能分析
  • 排序算法彙總

排序算法性能衡量

​ 排序算法有很多種，那麼如何來衡量一種排序算法的性能是否适合運用到真實場景中就是一個很現實的問題。對于内部排序來說，排序算法的性能主要受3個方面的影響。

1. 時間複雜度
2. 空間複雜度
3. 算法的複雜性

對于時間複雜度，排序是資料進行中經常執行的一種操作，屬于系統的核心部分，是以排序算法的事件開銷是衡量其好壞的最重要的标志。根據前面對于排序算法的解析，高效率的排序算法應該是具有盡可能少的關鍵字比較和盡可能少的記錄移動次數。

對于空間複雜度，評價一個排序算法的另一個主要名額是執行算法所需要的輔助空間，輔助空間是除了存放待排序所占用的存儲空間外，執行算法所需要的其他存儲空間。

對于算法的複雜性，這裡指的主要是算法本身的複雜度，即一個算法是否備援等。

​ 除了上述關于性能的衡量之外，關于排序算法還有一個可以考慮在内的東西，即排序的穩定性。

​ 如果在記錄序列中有兩個記錄 r [ i ] r[i] r[i]和 r [ j ] r[j] r[j]，它們的關鍵字 k e y [ i ] = = k e y [ j ] key[i]==key[j] key[i]==key[j]，且在排序之前，記錄 r [ i ] r[i] r[i]排在 r [ j ] r[j] r[j]前面。那麼如果在排序之後，記錄 r [ i ] r[i] r[i]仍然是排在記錄 r [ j ] r[j] r[j]前面，那麼就稱這個排序算法是穩定的。

​ 算法的穩定性主要也就是展現在相同元素之間的排列順序，隻要排序前後的相同元素之間的相對位置沒有改變即可。

冒泡排序

​ 冒泡排序是對于初學者來說最先接觸到的一種排序方法，這種排序方法實作起來較為簡單，接下來按照升序的規律來對冒泡排序進行講解。

冒泡排序-算法原理

​ 冒泡排序就是待排序列中相鄰的兩個數進行比較，根據一定的判斷條件來判斷是否交換，這裡我們考慮資料是升序排序，即要将資料從小到大排列，是以在每一趟冒泡排序的過程中，待排序列中的相鄰資料兩兩進行比較，如果前面的資料大于後面的資料，則交換這兩個資料，以此類推，一直比較到待排序列的最後一個元素。根據這一操作，我們可以得出每一趟冒泡排序之後，待排序列的最後一個元素總是待排序列中最大的那個元素，即剩下的資料中的最大值。是以在下一輪排序時，上一輪的最後一個資料已經是排好序的有序資料，不必再參與排序。

​ 例如： n n n個資料使用冒泡排序，一開始這 n n n個資料全部屬于待排資料，第一趟排序時，第一個數和第二個數比較，看是否交換，然後第二個數和第三個數比較，看是否交換……，直到 n − 1 n-1 n−1個數和第 n n n個數比較。此時，這 n n n個數中最大的數已經在最後一個位置上了，以此類推，第二輪排序隻需對前 n − 1 n-1 n−1個資料進行冒泡排序，第二輪結束後前 n − 1 n-1 n−1個資料的最大數在倒數第二個位置上……，直到第 n − 1 n-1 n−1趟，隻剩下了一個資料待排，不需要再排序，即此時的序列就是有序序列。

​ 故冒泡排序的原理就是關鍵字小的記錄不斷上浮（到前面來），關鍵字大的記錄不斷下沉（每趟排序最大的一直沉到底）。第 i i i輪排序将第 i i i大的記錄放在倒數第 i i i個位置。

​ 接下來通過2個簡單的例子來進行解釋：

冒泡排序-算法實作

​ 代碼實作也較為簡單，由于每次隻将一個最大的資料移動到最右邊，那麼對于 n n n個資料，隻需要找出前 n − 1 n-1 n−1個最大的就可以了，故外層需要 n − 1 n-1 n−1次循環。對于内層循環，每次在待排序列中使用相鄰元素比較和交換的方法，将目前一輪中待排序列的最大元素移動到最右邊加入到有序序列中。

// 冒泡排序
void BubbleSort(int data[], int n)
{
    // 外層n-1次循環，每次循環将最大的元素移到最右邊
    for (int i = 0; i < n; i++)
    {
        // 将剩餘無序序列的最大值移到無序序列的最右邊
        for (int j = 0; j < n - i - 1; j++)
        {
            if (data[j] > data[j + 1])  // 相鄰兩個數字進行比較
                swap(data[j], data[j + 1]);
        }
        // display(data, n);
    }
}
           

​ 但是對于上述冒泡排序來說，還有一些可以改進的地方，即有些時候資料并沒有那麼無序，當進行了幾輪循環之後整體資料就已經是有序了，那麼此時就沒有必要繼續進行排序。對于冒泡排序來說，隻要在找待排序列中最大元素時，沒有發生交換，那麼就說明此時的待排序列就已經是有序的了，故在上述代碼中加上部分内容即可。

// 冒泡排序2.0
void BubbleSort_(int data[], int n)
{
    // 外層n-1次循環，每次循環将最大的元素移到最右邊
    for (int i = 0; i < n; i++)
    {
        int flag = 0;   // 判斷目前輪次是否發生了交換
        // 将剩餘無序序列的最大值移到無序序列的最右邊
        for (int j = 0; j < n - i - 1; j++)
        {
            if (data[j] > data[j + 1])  // 相鄰兩個數字進行比較
            {
                swap(data[j], data[j + 1]);
                flag = 1;   // 發生了交換
            }
                
        }
        if (flag == 0)  // 若沒有交換則說明已經有序
            break;
        // display(data, n);
    }
}
           

冒泡排序-性能分析

​ 對于冒泡排序，最好的情況是在記錄的初始排列已經按關鍵字從小到大排好序時,此算法隻執行一趟起泡,做 n − 1 n-1 n−1次關鍵字比較,不移動記錄。

​ 最壞的情況是執行 n − 1 n-1 n−1趟起泡,第 i i i趟做 n − i n-i n−i次關鍵字比較, 執行 n − i n-i n−i次記錄交換。

​ 冒泡排序的時間複雜度為 O ( n 2 ) O(n^2) O(n2)，空間複雜度為 O ( 1 ) O(1) O(1)，且冒泡排序是一種穩定的排序方法。

選擇排序

​ 選擇排序也是初學排序算法中與冒泡排序一起進行學習的一種簡單的排序算法。該算法實作起來也很簡單，接下來以升序排序為例對選擇排序算法進行學習。

選擇排序-算法原理

​ 選擇排序也是将整體序列分為待排序列和有序序列，初始時待排序列就是原本的序列，有序序列為空，之後通過不斷的“選擇”，将待排序列中最小的元素添加到有序序列中。在每一趟排序中，從待排序列中選出一個最小數，然後讓其和待排序列的第一個資料交換。例如： n n n個資料排序，第一趟排序時所有的資料都是待排序列，然後找出其中的最小數，讓其和待排序列的第一個資料交換，則在第二趟排序時，第一個元素已經是有序序列，是以第二趟排序時待排序列則不包含第一趟已經排好的第一個元素了，待排序列中隻包含後面的 n − 1 n-1 n−1個元素。以此類推，第3趟排序時待排序列中不包含前兩趟排序中已經排好的兩個元素……第 n − 2 n-2 n−2趟排序時有序序列已經有 n − 3 n-3 n−3個元素，隻剩3個元素待排，第 n − 1 n-1 n−1趟時隻剩2個元素待排，第 n − 1 n-1 n−1趟排序完成後，待排序列隻剩下一個元素，其中最小的元素就是它自己，是以不需要再排序，即整個序列已經是有序序列了。

​ 接下來通過兩個例子來對選擇排序的過程有一個更進一步的了解。

選擇排序-算法實作

​ 每經過一趟排序，有序序列中的元素個數會加1，待排序列中的元素個數會減少1，而當待排序列中隻剩下最後一個元素時，則無需再繼續排序，此時的整個序列就是一個有序序列，即完成了整個排序的過程，是以可知 n n n個資料進行選擇排序需要内部排 n − 1 n-1 n−1趟。

​ 對于每一趟排序，我們都需要從待排序列中選出一個最小數，将其與待排序列的第一個元素交換。是以我們假定目前的最小數就是待排序列的第一個元素的位置，假定儲存資料的數組為 d a t a [   ] data[\ ] data[ ], m i n i n d e x minindex minindex指向待排序列中最小數的數組下标，則我們在初始化時，講 m i n i n d e x minindex minindex初始化為 i i i，然後從待排序列的第二個數開始比較（即從 d a t a [ i + 1 ] data[i+1] data[i+1]開始比較），如果遇到比 d a t a [ m i n i n d e x ] data[minindex] data[minindex]還小的數，記為 d a t a [ j ] data[j] data[j]，則令 m i n i n d e x = j minindex=j minindex=j，以此類推，周遊待排序列，得到待排序列中最小數的下标，然後再交換 d a t a [ i ] data[i] data[i]與 d a t a [ m i n i n d e x ] data[minindex] data[minindex]的值，即完成了一趟排序。

​ 代碼實作如下所示。

// 簡單選擇排序
void SelectSort(int data[], int n)
{
    // 外層循環，需要找出前n-1個最小的資料
    for (int i = 0; i < n - 1; i++)
    {
        int min_index = i;  // 目前輪次中的最小元素（初始化）
        // 在後面的無序序列中找到最小的
        for (int j = i + 1; j < n; j++)
        {
            if (data[min_index] > data[j])  // 判斷是否有更小的元素
                min_index = j;
        }
        // 将目前一輪最小的元素放置到無序序列的第一個位置
        swap(data[min_index], data[i]);
        // display(data, n);
    }
}
           

選擇排序-性能分析

​ 對于選擇排序，它不能像冒泡排序那樣中途判斷出目前是否已經不需要再繼續執行排序算法，故對于選擇排序來說，外層循環的 n − 1 n-1 n−1次必不可少，但是對于内層循環，可能不需要比較，也可能需要比較 n − i n-i n−i次。

​ 故選擇排序的時間複雜度也是 O ( n 2 ) O(n^2) O(n2)，空間複雜度為 O ( 1 ) O(1) O(1)，且選擇排序是不穩定的排序算法，例如對于序列 5 ∗   5   1   7 5^*\ 5\ 1\ 7 5∗ 5 1 7，通過選擇排序得到的序列為 1   5   5 ∗   7 1\ 5\ 5^*\ 7 1 5 5∗ 7。

直接插入排序

​ 直接插入排序顧名思義，就是将待排序列逐個插入到有序序列中，使得最終得到的序列是有序的。直接插入排序是最簡單最直覺的一種排序方法。接下來以升序為例對該排序算法進行學習。

直接插入排序-算法原理

​ 在實作插入排序時，可以考慮建立一個臨時空間用于儲存有序序列，然後通過大小關系找到插入位置并按照順序表的插入方式進行插入操作。這樣做可以但是相對來說所需要的空間複雜度較高，那麼是否可以考慮在原資料的基礎上不建立臨時空間來進行排序呢？

​ 這裡還是将原序列分為兩個部分，即有序序列和待排序列。插入排序就是先将資料分為兩個序列，左邊為已經排好序的有序序列，右邊為待排序列，每趟排序就将待排序列中的第一個元素插入左邊的待排序列中來。例如：第一趟排序時，假設第一個元素已經是排好序的，則第一趟排序就是将第二個元素插入前面的有序序列中，插入時将要插入的資料逐個與它前面的數比較（從右往左比較），如果遇到比它大的資料，則那個資料後移一位，直到遇到比它小的資料，在空餘的那個位置上放上該待排資料即可；第二趟排序時即前面兩個元素已經排好序，将第三個元素從右往左比較，遇到比它小的資料時就插入，以此類推，直到序列中最後一個資料被插入到有序序列中即完成了排序。

​ 接下來通過兩個例子來對直接插入排序進行一個直覺的了解。

直接插入排序-算法實作

​ 根據上述原理，假設現在資料數組為 d a t a [   ] data[\ ] data[ ]，資料規模為n，由于我們一開始假設第一個元素為有序序列，是以我們隻需要對第2個至第 n n n個序列進行插入排序，即隻需要 n − 1 n-1 n−1次排序即可。而在每一趟排序中，例如在第 i i i趟排序中，我們需要插入 d a t a [ i ] data[i] data[i]，則我們首先需要把 d a t a [ i ] data[i] data[i]的位置空出來，以友善後面的元素後移，是以我們需要一個臨時變量 t e m p temp temp來存儲 d a t a [ i ] data[i] data[i]，空出位置後，我們開始比較，從右往左，即從 d a t a [ i − 1 ] data[i-1] data[i−1]比較，如果大于 d a t a [ i ] data[i] data[i]，則将該資料往後移動一個位置，然後繼續往左比較。如果遇到小于 d a t a [ i ] data[i] data[i]的資料，假設為 d a t a [ j ] data[j] data[j]，則此時， d a t a [ j + 1 ] data[j+1] data[j+1]應該時大于等于 d a t a [ i ] data[i] data[i]的，是以從 d a t a [ j + 1 ] data[j+1] data[j+1]到 d a t a [ i − 1 ] data[i-1] data[i−1]都是已經往右移動了一個位置，此時 d a t a [ j + 1 ] data[j+1] data[j+1]的位置應該時空的，是以将 d a t a [ i ] data[i] data[i]填入此處，即完成了第i個資料 d a t a [ i ] data[i] data[i]的插入。後面的資料以此類推。核心代碼如下圖所示。

void InsertSort(int data[], int n)
{
    // 假設第一個元素有序，故隻需要插入後續n-1個元素即可
    for (int i = 1; i < n; i++)
    {
        int temp = data[i]; // 目前需要插入的元素
        int j = i;  // 找到其在有序序列中應該在的位置
        for (; j > 0; j--)  // 從後往前找，找到第一個小于它的元素，大于它的元素全部後移
        {
            if (temp < data[j - 1]) // 大于它，應該後移
                data[j] = data[j - 1];
            else // 小于，說明找到了位置，退出
                break;
        }
        data[j] = temp; // 插入對應位置即可
    }
}
           

直接插入排序-性能分析

​ 對于直接插入排序，其關鍵字比較次數和記錄移動次數與初始的排列有關。

​ 最好的情況下，排序前記錄已經按照關鍵字從小到大有序，每趟隻需要與前面有序記錄序列的最後一個記錄比較一次即可。

​ 最壞的情況下，第 i i i趟時第 i i i個記錄必須與前面 i i i個記錄都要進行比較，且每進行一次比較都需要進行一次資料移動。

​ 故直接插入排序的時間複雜度是 O ( n 2 ) O(n^2) O(n2)，空間複雜度是 O ( 1 ) O(1) O(1)，且直接插入排序是一種穩定的排序算法。

​ 值得一提的是，直接插入排序最大的有點在于簡單，在記錄數較少時，是一個比較好的排序方法。

希爾排序

​ 希爾排序出現的目的是為了改進直接插入排序，使得算法的效率獲得提升。故希爾排序也可以了解為是改進版的直接插入排序。接下來還是以升序作為排序規律，對希爾排序進行學習。

希爾排序-算法原理

​ 根據前面對于直接插入排序的分析，當初始序列基本有序時，直接插入排序的效率就會較高。很顯然我們不能控制初始序列是否基本有序，能做的就是通過一定的操作使得初始序列基本有序。而希爾排序就是在直接插入排序的基礎上，先通過分組插入排序的方法，使得整個序列基本有序。

​ 首先對基本有序有一個大概的了解，這裡指的是關鍵字小的元素基本在前面，關鍵字大的元素基本在後面，這就是基本有序。希爾排序方法是先将排序列分成若幹子序列分别進行插入排序，待整個序列基本有序時，再對全體記錄進行一次直接插入排序。具體流程如下所示。

1. 首先取一個整數 g a p gap gap， g a p < n gap < n gap<n(待排序記錄數) 作為間隔, 将全部記錄分為 g a p gap gap個子序列, 所有距離為 g a p gap gap 的記錄放在同一個子序列中。
2. 在每一個子序列中分别施行直接插入排序。
3. 然後縮小間隔 g a p gap gap, 例如取 g a p = g a p / 2 gap = gap/2 gap=gap/2。
4. 重複上述的子序列劃分和排序工作，直到最後取 g a p = 1 gap = 1 gap=1, 将所有記錄放在同一個序列中排序為止。

對上述分組這裡稍作一點額外解釋，例如對于序列9,1,5,8,3,7,4,6,2。如果按照希爾排序的方法将其分為三組，則這三組分别是 [ 9 , 8 , 4 ] [9,8,4] [9,8,4]， [ 1 , 3 , 6 ] [1,3,6] [1,3,6]， [ 5 , 7 , 2 ] [5,7,2] [5,7,2]。之後再每個序列中執行直接插入排序即可。

​ 接下來通過一個具體例子對希爾排序有一個直覺的了解。

希爾排序-算法實作

​ 實作時較為簡單，直接按照前面的流程進行實作即可。通過一個外層循環來控制子序列元素之間的間隔，在固定了子序列元素間隔之後，就可以使用直接插入排序對每個子序列進行插入排序。這樣一來就可以實作基本有序，當 g a p = 1 gap=1 gap=1的時候其實就是執行了一次直接插入排序。

// 希爾排序
void ShellSort(int data[], int n)
{
    // 不斷縮小間隔
    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        // 内部對于每個序列，執行一次直接插入排序
        for (int i = gap; i < n; i++)
        {
            int temp = data[i];
            int j = i;
            for (; j >= gap && data[j - gap] > temp; j -= gap)
            {
                data[j] = data[j - gap];
            }
            data[j] = temp;
        }
        // display(data, n);
    }
}
           

希爾排序-性能分析

​ 對于希爾排序算法，它的性能和效率主要取決于這個間隔應該怎麼取以及怎麼進行疊代。

​ 希爾排序的時間複雜度約為 O ( n ( log ⁡ 2 n ) 2 ) O(n\left( \log _{2}^{n} \right) ^2) O(n(log2n​)2)，空間複雜度為 O ( 1 ) O(1) O(1)，且希爾排序是一個不穩定的排序算法，因為在分組之間有跳躍式的插入。

快速排序

​ 快速排序可以說是衆多排序算法中最熱門的一個排序算法，應用場景十分廣泛。在我個人的了解中，快速排序采取的是一種類似于疊代法的思路來進行排序求解，總體來說是對于冒泡排序的一個很大的改進。接下來以升序為排序規則，來對快速排序進行學習。

快速排序-算法原理

​ 快速排序就是選擇一個元素當作基準，通常都是選擇待排序列中的第一個元素作為目前待排序列的基準。然後根據選取的基準元素進行分區，分為左右兩個子序列，其中左序列中的所有元素均小于基準元素，右序列中的所有元素均大于基準元素，此時的基準元素應該再整個待排序列的中間，也是在完成排序後它所在的位置。以此類推，對左右子序列重複上述過程，直到所有的元素就被放在完成排序後它所在的位置上。

​ 在将待排序列以基準元素為為标準劃分左右序列的時候，先将基準元素拿出，然後從數組右端開始比較，如果遇到小于基準元素的，則将該數填到基準元素的位置上去，此時剛剛填入的資料的原來的位置又是空的，此時再回到左端，不斷進行比較，直到比較完所有的元素，最後剩餘的那個待填的位置就是基準元素最後應該在的位置。

​ 接下來通過兩個例子來對快速排序中某一次排序過程有一個了解。

接下來通過一個例子對快速排序整個過程進行了解。

快速排序-算法實作

​ 根據上述原理，我們不難得出快速排序的實作方法，假設待排序列為 d a t a [   ] data[\ ] data[ ]，一共有 n n n個元素。在第一趟排序中，我們的基準為 d a t a [ 0 ] data[0] data[0]，我們定義兩個變量 l o w low low， h i g h high high用來指向數組下标，初始化時 l o w = 0 , h i g h = n − 1 low=0,high=n-1 low=0,high=n−1，即 l o w low low應該指向待排序列的左端點，也是本趟排序中的基準點，而 h i g h high high應該指向待排序列的右端點。

由于我們基準選的是左端點，是以我們比較時應該從右端點開始比較，即判斷 d a t a [ h i g h ] data[high] data[high]與基準資料的關系，如果大于基準元素，則 h i g h − − high-- high−−，直到遇到比基準小的數或循環結束；反之，則将 h i g h high high處的元素放在 l o w low low處，即 d a t a [ l o w ] = d a t a [ h i g h ] data[low]=data[high] data[low]=data[high]，然後從 l o w low low處開始與基準比較。從 l o w low low處開始比較時，如果遇到小于基準的數，則 l o w + + low++ low++，直到遇到比基準大的數或循環結束，反之，将該數移到 h i g h high high對應的位置，即 d a t a [ h i g h ] = d a t a [ l o w ] data\left[high\right]=data\left[low\right] data[high]=data[low]，然後重新回到 h i g h high high處開始比較。重複上述過程，直到最終 l o w low low與 h i g h high high重合或 l o w > h i g h low>high low>high。

第一趟排序結束後，傳回第一趟排序中基準元素的位置，作為下一次左序列的右端點和右序列的左端點。以此類推，不停的對左序列和右序列進行上述操作，直至所有的元素放在其該有的位置上。代碼如下所示。

// 快速排序
int Quick(int data[], int low, int high)
{
    int temp = data[low];   // 目前基準元素，一般選擇第一個元素
    while (low < high)  // 周遊目前序列中所有元素
    {
        // 從右側開始往左找，判斷是否都大于基準元素，直到找到第一個小于的
        while (data[high] > temp && low < high)
            high--;

        data[low] = data[high]; // 将小于基準元素的資料放在基準元素的位置上
        
        // 從左往右找，找到第一個大于基準元素的
        while (data[low] < temp && low < high)
            low++;

        // 将該元素放在高處空位上
        data[high] = data[low];

    }
    data[low] = temp;   // 最後一個空位放基準元素
    return low; // 傳回基準元素的位置
}


// 快速排序主程式
void QuickSort(int data[],int n, int low, int high)
{
    // 區間要大于等于2
    if (low < high)
    {
        // 找到目前基準元素的位置
        int mid = Quick(data, low, high);
        // display(data, n);

        // 對左序列進行分類
        QuickSort(data, n, low, mid - 1);

        // 對右序列進行分類
        QuickSort(data, n, mid + 1, high);

    }
}
           

快速排序-性能分析

​ 對于快速排序，由于快速排序是一個遞歸的過程，是以快速排序的趟數取決于遞歸樹的深度。

​ 最好的情況，每次都取到中點，這樣的時間複雜度是 O ( n log ⁡ 2 n ) O(n\log _{2}^{n}) O(nlog2n​)，最壞的情況，每次都取到端點值，時間複雜度是 O ( n 2 ) O(n^2) O(n2)。

​ 快速排序的空間複雜度為 O ( log ⁡ 2 n ) O(\log _{2}^{n}) O(log2n​)，這裡的空間主要是用于遞歸的棧空間。快速排序是不穩定的排序算法。

堆排序

​ 前面介紹到希爾排序是直接插入排序的改進算法，快速排序是冒泡排序的改進算法，而堆排序則是選擇排序的改進算法。改進點主要在于減少了一些重複的比較，在選擇排序中，每次找出最小的一個放在最左邊，之後再找出另一個最小的元素，在查找過程中，很多比較過程前面已經執行過了，不需要再重複比較，堆排序就很好了解決了這個問題。

​ 接下來還是以升序排序為例，對堆排序進行學習。

堆排序-算法原理

​ 在介紹堆排序算法的原理之前，首先要搞清楚什麼是“堆”。設有一個關鍵字集合，按照完全二叉樹的順序存儲方式存放在一個一維數組中，對它們從根開始，自頂向下，同一層自左向右從1開始連續編号。若滿足 K i ⩾ K 2 i & & K i ⩾ K 2 i + 1 K_i\geqslant K_{2i} \&\& K_i\geqslant K_{2i+1} Ki​⩾K2i​&&Ki​⩾K2i+1​，則稱該關鍵字集合構成一個最大堆（大頂堆），如果上述定義中的大于等于換成小于等于，則構成一個最小堆（小頂堆）

​ 上述定義其實也可以這樣來了解，堆其實就是一種完全二叉樹，對于最大堆，每個結點的值都大于等于其左右孩子的值；對于小頂堆，每個結點的值都小于等于其左右孩子的值。

​ 那麼在有了這麼一個堆之後，有什麼用呢，暫時先不考慮如何建立這樣的一個堆，假設我們已經知道如何調整這個二叉樹，使其變成一個大頂堆或者小頂堆。根據前面提到的性質，我們知道對于大頂堆來說，整個序列中最大的元素就是在根部，對于小頂堆來說，整個序列中最小的元素就是在根部。這樣一來相當于我們已經知道了其中一個極值的存在，這裡就可以引入選擇排序的思路，找到這個極值元素之後，例如大頂堆，将根部元素和最後一個元素進行交換，那麼最大的元素就放在了最後一個位置，這樣一來就相當于排好了一個元素。但是交換之後這個堆肯定就不是大頂堆了，因為根節點變成了一個很小的元素，故這裡需要重新調整，同時已經交換過的元素，即前面提到的極值元素，此時已經不算在大頂堆中了，它屬于有序元素，不需要繼續參與排序了。

​ 根據上面的思路，不斷的将根節點與大頂堆最後一個無序序列位置進行交換，然後重新調整堆為大頂堆，這樣一來就可以将每個無序序列中的最大的元素添加到有序序列中，因為是按照從後往前的順序放，并且先放的是大資料，故最終得到的一個序列應該是升序的。這就是堆排序的思路和過程。

​ 那麼在對堆排序有一個大緻的了解之後，接下來就基本清楚了堆排序所需要解決的問題，第一個就是如何初始化一個大頂堆，第二個就是在交換元素之後如何調整堆使其重新變成一個大頂堆。

、對于第一個問題，即如何初始化一個大頂堆。因為最終需要滿足的是，每個結點的值都要大于左右孩子的值，那麼就很簡單了，對于每一個結點，将結點值與左右孩子值放在一起進行比較，将結點值與左右孩子中大于結點值的且最大的那一個值與結點值進行交換即可。同時，初始化時應該從下往上初始化，如果從上往下的話，下面交換完成之後不能確定上層的是否仍然保持大頂堆的性質，且重新調整起來較為麻煩。如果從下往上進行調整，雖然上層交換完成之後可能會使得下層不滿足大頂堆性質，但是根據樹的性質通路起來較為友善，可以直接重新調整。

​ 在調整時，根據前面的調整政策，在初始化時隻需要對于有孩子的結點進行調整即可，根據 2 i = n 2i=n 2i=n可以計算出從編号為 n 2 \frac{n}{2} 2n​，因為該結點的左孩子剛好越界，即代表該節點是第一個沒有葉子結點的。之後通過往前周遊，對于每個點進行調整即可，調整時如果發生了交換，則需要繼續往下判斷是否影響了之前的調整，如果有的話則需要重新調整。

​ 接下來通過一個例子對于初始化最大堆進行進一步的了解。

​ 對于第二個問題，即交換根節點與最後一個結點之後，如何重新調整回大頂堆。有了第一問的基礎，這個就很簡單了，由于隻發生了一個點的交換，故隻需要對于根節點重新進行一次調整即可。

​ 接下來通過一個例子對于重新調整進行進一步了解，此時49與8已經發生了交換，49被移除大頂堆的範圍。

​ 接下來通過一個例子對于堆排序的整個過程進行了解。

堆排序-算法實作

​ 根據前面的分析，首先實作對某個結點進行調整，這個過程需要不斷的往下進行，應該使用遞歸的方式。但是由于這裡的樹是使用數組進行存儲的，故也可以使用循環來進行實作，兩種方式均可以。在實作時重點就在于找出結點，結點左右孩子中最大的結點，如果孩子中有大于結點的值，交換其中最大的即可，同時繼續往下調整；如果沒有大于結點的值，則說明本身符合大頂堆的要求，也不用繼續往下。

​ 遞歸實作的代碼如下所示。

// 調整堆(遞歸)
void adjust_(int data[], int index, int n)
{
    int left = 2 * index + 1;   // 左孩子
    int right = 2 * index + 2;  // 右孩子
    int maxIndex = index;   // 最大的結點
    // 找出三個值中最大的
    if (left < n && data[left] > data[maxIndex])
        maxIndex = left;
    if (right < n && data[right] > data[maxIndex])
        maxIndex = right;
    // 判斷是否要發生交換
    if (maxIndex != index) 
    {
        swap(data[index], data[maxIndex]);  // 交換
        adjust_(data, maxIndex, n); // 繼續往後調整
    }
}
           

​ 非遞歸實作的代碼如下所示。

// 調整堆(非遞歸)
void adjust(int data[], int index, int n)
{
    int s;  ///大頂堆，升排列
    while (2 * index + 1 < n)   // 是否到了葉子結點
    {
        s = 2 * index + 1;  // 左孩子
        // 有右孩子且右孩子比左孩子大
        if (s + 1 < n && data[s] < data[s + 1])
            s++;    // 取右孩子
        // 判斷是否要交換
        if (data[index] < data[s])  // 需要交換
        {
            swap(data[index], data[s]); // 交換
            index = s;  // 繼續往後調整
        }
        else // 不需要交換
            break;
    }
}
           

​ 在實作了調整代碼之後，接下來就是需要實作代碼的主體部分，首先肯定是需要初始化一個大頂堆，這個使用一個循環從 n 2 \frac{n}{2} 2n​除逐個往前調整即可。初始化完成之後，接下來就可以将根節點與最後一個結點進行交換，然後此時就相當于排好了一個元素，那麼接下來從根節點重新調整，同時注意已經排好序的元素不能被算在大頂堆中，故這個過程通過一個循環即可完成。代碼如下所示。

// 堆排序
void HeapSort(int data[], int n)
{
    // 初始化堆
    for (int i = n / 2; i >= 0; i--)
    {
        adjust(data, i, n);
    }
    // display(data, n);
    // 排序
    for (int i = 1; i < n; i++)
    {
        swap(data[0], data[n - i]); // 堆頂出去，最底下的一個上來
        adjust(data, 0, n - i); // 重新調整
        // display(data, n);
    }
}
           

堆排序-性能分析

​ 對于一個長度為 n n n的序列，其對應的完全二叉樹的深度為 k ( 2 k − 1 ⩽ k ⩽ 2 k ) k(2^{k-1} \leqslant k \leqslant 2^k) k(2k−1⩽k⩽2k)，故在每一次調整的時候，關鍵字比較次數最多為 2 ( k − 1 ) 2(k-1) 2(k−1)次。堆排序時間主要耗費在初始化堆和每次交換之後重新調整堆上。

​ 初始化建堆時最多做 n 2 \frac{n}{2} 2n​次調整，排序最多需要做 n − 1 n-1 n−1次調整，故時間複雜度為 O ( n k ) O(nk) O(nk)，平均下來就是 O ( n log ⁡ 2 n ) O(n\log _{2}^{n}) O(nlog2n​)。空間複雜度為 O ( 1 ) O(1) O(1)。

​ 堆排序是一個不穩定的排序算法。

歸并排序

​ 歸并排序也成為合并排序，采用的是分治法的思想，即将一個大問題分解成許多的小問題。在這裡就是将原來的待排序列分解成很多個小序列，進行排序，然後逐漸合并這些小序列，實作總體的排序，這裡我們采用二路歸并排序，同時以升序作為排序規則對歸并排序進行學習。

歸并排序-算法原理

​ 歸并排序中，歸并的意思是将兩個或兩個以上的有序表合并成一個新的有序表。那麼再結合歸并排序的思想，那麼在初始時就可以将原始序列中的每一個元素都看到一個序列，即 n n n個元素就是 n n n個序列，那麼每個序列内部就是有序的（因為每個序列自己）。之後歸并排序的問題就變成了如何合并兩個有序序列。

​ 在合并兩個有序序列時，要注意這裡的有序序列，故在合并時其實其實兩個序列都從頭開始周遊，然後逐個進行比較，将目前較小的一個元素添加到新序列中，并從原序列中彈出，然後将原序列中下一個元素與另一個序列之前的元素進行比較。以此類推，直到一方沒有元素了為止。但是這裡還可能有一個問題，就是某一方在比較完成之後還有剩餘，那麼這些剩餘可以直接添加到新的有序序列的尾部。

​ 有序序列合并過程如下所示。

​ 那麼對于歸并排序來說，首先将待排序列中的每個序列看作一組，即一開始 n n n個資料分成 n n n組，然後開始合并，兩兩合并為一個新的組，然後新合并的組再兩兩合并，一直重複這個工作，直到隻剩下最後一個組，該組就是最後完成排序後的有序序列。這裡需要說的是，合并的過程并不是去利用一些排序算法去排序，而是建立兩個臨時數組，根據大小關系，利用前面的合并有序序列思路，一個一個的放進原數組中。

​ 接下來通過一個例子來對歸并排序有一個更進一步的了解。

歸并排序-算法實作

​ 在實作歸并算法時，這裡以2路歸并為例，那麼第一輪中每個小數組的長度就是1，第二輪中每個小數組的長度就是2，第三輪就是4，第四輪就是8，…。那麼就可以得出對于一個長度為 n n n的序列，需要經曆的長度變化最大為 log ⁡ 2 n \log _{2}^{n} log2n​。

​ 在确定了每一次歸并的數組長度之後，在具體實作時，主要是将相鄰兩個數組進行合并，在确定到每個數組的上下界之後，直接調用合并算法即可。但是處理數組上下界的時候可能會遇到問題，例如通過長度計算出來的數組下界下标會越界，這是将下界下标設定為 n − 1 n-1 n−1即可。

// 歸并算法合并部分
void Merge(int data[], int begin, int mid, int end)
{
    int left = mid - begin + 1; // 左半邊數組元素個數
    int right = end - mid;  // 右半邊數組元素個數

    int data_left[100]; // 存放左半邊數組元素
    int data_right[100];    // 存放右半邊數組元素

    // 對左半邊數組指派
    for (int i = 0; i < left; i++)
        data_left[i] = data[begin + i];
    // 對右半邊數組指派
    for (int i = 0; i < right; i++)
        data_right[i] = data[mid + 1 + i];

    int i = 0;  // 左半邊數組指針
    int j = 0;  // 右邊版數組指針
    int count = begin;  // 重新合并到原數組中，指向原數組的指針

    // 同時周遊
    while (i < left && j < right)
    {
        if (data_left[i] < data_right[j])   // 左半邊資料更小，則添加左半邊資料
        {
            // 同時下标指針都移動
            data[count++] = data_left[i++];
        }
        else    // 右半邊資料更小，則添加右半邊資料
        {
            // 同時下标指針都移動
            data[count++] = data_right[j++];
        }
            
    }
    // 若左邊有空餘未添加進去，則将剩餘的添加進去
    while (i < left)
    {
        data[count++] = data_left[i++];
    }
    // 若右邊有空餘未添加進去，則将剩餘的添加進去
    while (j < right)
    {
        data[count++] = data_right[j++];
    }

}

// 2路歸并排序
void MergeSort(int data[], int n)
{
    // 控制間隔i，從1開始以2的倍數增加
    for (int i = 1; i < n; i *= 2)
    {
        /*
        * 每次循環中，将原本的大數組分為了若幹個長度為i的小數組
        * 相鄰兩個數組之間進行合并操作
        */
        // 将相鄰相鄰兩個數組進行合并，故beign每次加2i
        for (int begin = 0; begin < n; begin += 2 * i)
        {
            int mid = begin + i - 1;    // 第一個數組末尾下标
            if (mid >= n)   // 越界判斷
            {
                mid = n - 1;
            }
            int end = begin + 2 * i - 1;    // 第二個數組的末尾下标
            if (end >= n)   // 越界判斷
            {  
                end = n - 1;
            }
            // 兩個數組合并
            Merge(data, begin, mid, end);   
        }
        // display(data, n);
    }
}
           

歸并排序-性能分析

​ 對于歸并排序，如果待排記錄為 n n n個，那麼就需要做 log ⁡ 2 n \log _{2}^{n} log2n​趟歸并排序。對于每趟兩路歸并排序，其實都是分為了 n 2 i \frac{n}{2i} 2in​組，故内層循環複雜度可以看作 O ( n ) O(n) O(n)。

​ 是以對于歸并排序算法來說，時間複雜度為 n log ⁡ 2 n n\log _{2}^{n} nlog2n​，同時在合并時也可以看出，這裡是需要将左右兩個小數組的元素取出儲存在額外的空間中，且小數組的長度是 O ( n ) O(n) O(n)，故空間複雜度為 O ( n ) O(n) O(n)。

​ 同時歸并排序也是一種穩定的排序方法。

排序算法彙總

​ 最後對上述算法進行一個簡單的彙總，如下表所示。

排序方法	平均時間	最好情況	最壞情況	輔助存儲	是否穩定	适合情況
冒泡排序	O ( n 2 ) O(n^2) O(n2)	O ( n ) O(n) O(n)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	穩定	記錄數不多
選擇排序	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	穩定	較多
插入排序	O ( n 2 ) O(n^2) O(n2)	O ( n ) O(n) O(n)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	穩定	記錄數不多
希爾排序	O ( n ( log ⁡ 2 n ) 2 ) O(n\left( \log _{2}^{n} \right) ^2) O(n(log2n​)2)	O ( n 1.3 ) O(n^{1.3}) O(n1.3)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	不穩定	不太多
快速排序	O ( n log ⁡ 2 n ) O(n\log _{2}^{n}) O(nlog2n​)	O ( n log ⁡ 2 n ) O(n\log _{2}^{n}) O(nlog2n​)	O ( n 2 ) O(n^2) O(n2)	O ( log ⁡ 2 n ) O(\log _{2}^{n}) O(log2n​)	不穩定	較多
堆排序	O ( n log ⁡ 2 n ) O(n\log _{2}^{n}) O(nlog2n​)	O ( n log ⁡ 2 n ) O(n\log _{2}^{n}) O(nlog2n​)	O ( n log ⁡ 2 n ) O(n\log _{2}^{n}) O(nlog2n​)	O ( 1 ) O(1) O(1)	不穩定	較多
歸并排序	O ( n log ⁡ 2 n ) O(n\log _{2}^{n}) O(nlog2n​)	O ( n log ⁡ 2 n ) O(n\log _{2}^{n}) O(nlog2n​)	O ( n log ⁡ 2 n ) O(n\log _{2}^{n}) O(nlog2n​)	O ( n ) O(n) O(n)	穩定	都可以