本篇文章對選擇排序中的簡單選擇排序與堆排序，以及常用的歸并排序做一個總結分析，

常見排序演算法總結分析之交換排序與插入排序-C#實作是排序演算法總結系列的首篇文章，包含了一些概念的介紹以及交換排序（冒泡與快速排序）和插入排序（直接插入與希爾排序）的總結，感興趣的同學可以先去看一下，

選擇排序

選擇排序主要包括兩種排序演算法，分別是簡單選擇排序和堆排序

簡單選擇排序

基本思想

每一趟在待排序列中選出最小（或最大）的元素，依次放在已排好序的元素序列后面（或前面），直至全部的元素排完為止，

簡單選擇排序也被稱為直接選擇排序，首先在待排序列中選出最小的元素，將它與第一個位置上的元素交換，然后選出次小的元素，將它與第二個位置上的元素交換，以此類推，直至所有元素排成遞增序列為止，

選擇排序是對整體的選擇，只有在確定了最小數（或最大數）的前提下才進行交換， 大大減少了交換的次數，

復雜度與穩定性與優缺點

• 空間復雜度：O(1)
• 時間復雜度：O(n²)
• 最好情況：O(n²)，此時不發生交換，但仍需進行比較
• 最壞情況：O(n²)
• 穩定性：不穩定，因為在將最小或最大元素替換到前面時，可能將排在前面的相等元素交換到后面去
• 優點：交換資料的次數已知(n - 1)次
• 缺點：不穩定，比較的次數多

演算法實作

public void SimpleSelectionSort(int[] array){
    for(int i = 0; i < array.Length - 1; i ++){
        int index = i;
        for(int j = index + 1; j < array.Length; j ++){
            if(array[j] < array[index]){
                index = j;
            }
        }
        if(index != i)
            Swap(array, i, index);
    }
}

public void Swap(int[] array, int i, int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

【演算法解讀】

初始時無序區為整個待排序列，演算法內層回圈遍歷整個無序區的所有元素，找到其中最小的元素，用index記錄其下標位置，然后將找到的最小元素與無序區的首元素進行交換，這樣就完成了一趟選擇排序，此時序列的首元素處于有序區中，剩下的元素處于無序區中，重復上面的操作，繼續查找無序區中的最小元素，并將找到的最小元素和無序區首元素進行交換，直至完成所有排序，

【舉個栗子】

對于待排序列3,1,4,2
首先將序列首元素3的索引0保存在index中，從元素1開始與index位置上的元素（此時是3）進行比較，1<3，則index保存元素1的索引，繼續將index位置上的元素（此時是1）與元素4比較，4>1，繼續與2比較，1<2，不需要改變，沒有需要再比較的元素了，此時將index記錄的索引位置上的元素3和無序區首元素進行交換，則完成一趟選擇排序.，序列為1,3,4,2，有序區為1，無序區為3,4,2，繼續下一趟排序，將找到的無序區最小元素，和無序區首元素進行交換，這一趟選擇排序結束后，序列為1,2,4,3，有序區為1,2，無序區為4,3，重復上述操作直到完成排序，

堆排序

堆排序是借助堆來實作的選擇排序，

什么是堆呢？堆是滿足下列性質的數列{ R₁, R₂, R₃, R₄, ..., R_n }：

R_i<=R_2i且Ri<=R_{2i + 1}或者是R_i>=R_2i且R_i>=R_{2i + 1}，前者稱為小頂堆，后者稱為大頂堆，

例如小頂堆：{10,34,24,85,47,33,53}，位置i（i從1開始）上的元素小于2i位置上的元素，且小于2i+1位置上的元素，繪制成堆的形狀，如下圖所示，可以發現每個堆的堆頂元素（每個二叉樹的根節點）均小于其左子節點（2i）與右子節點（2i + 1）元素，

對于小頂堆而言，整個堆的堆頂元素便是整個序列的最小值，大頂堆同理，

基本思想

對待排序列的所有元素，首先將它們排成滿足大頂堆或小頂堆的定義的序列，常稱為建堆，建堆完成后堆頂元素便是最大或最小元素，然后將堆頂元素移出（比如移動到序列尾部），再對剩余的元素進行再建堆，常稱為重新調整成堆，即可通過堆頂元素得到次大（次小）元素，如此反復進行，直到完成排序為止，

實作堆排序有兩個關鍵步驟，建堆和調整堆
如何建堆：首先將待排序列畫成一顆完全二叉樹，然后再把得到的完全二叉樹轉換成堆，
從最后一個有孩子節點的節點（這樣可以構成一顆有孩子的樹，根節點才能夠向下滲透）開始（對于陣列而言就是下標為n / 2 - 1的節點）），依次將所有以該節點為根的二叉樹調整成堆，即先調整子樹，再調整父樹，當這個程序持續到整顆二叉樹樹的根節點時，待排序列就被調整成了堆，即建堆完成，

如何調整堆：假設被調整的節點為A，它的左孩子為B，右孩子為C，那么當A開始進行堆調整時，根據上面建堆的方式，以B和以C為根的二叉樹都已經為堆，如果節點A的值大于B和C的值（以大頂堆為例），那么以A為根的二叉樹已經是堆，如果A節點的值小于B節點或C節點的值，那么節點A與值最大的那個孩子節點變換位置，此時需要繼續將A與和它交換的那個孩子的兩個孩子節點進行比較，以此類推，直到節點A向下滲透到適當的位置為止，

如果要從小到大排序，則使用大頂堆，如果要從大到小排序，則使用小頂堆，原因是堆頂元素需要交換到序列尾部

復雜度與穩定性與優缺點

• 空間復雜度：O(1)
• 時間復雜度：O(nlog₂ⁿ)
• 最好情況：O(nlog₂ⁿ)
• 最壞情況：O(nlog₂ⁿ)，它的最壞情況接近于平均性能
• 穩定性：不穩定
• 優點：在最壞情況下性能優于快速排序，由于在直接選擇排序的基礎上利用了比較結果形成堆，效率提高很大，
• 缺點：不穩定，初始建堆所需比較次數較多，因此記錄數較少時不宜采用

演算法實作

public void HeapSort(int[] array){
    // 建堆
    for(int i = array.Length / 2 - 1; i >= 0; i --){
        BuildHeap(array, i, array.Length - 1);
    }
    // 調整堆
    for(int i = array.Length - 1; i > 0; i --){
        Swap(array, 0, i);
        BuildHeap(array, 0, i - 1);
    }
}

public void BuildHeap(int[] array, int left, int right){
    int target = array[left];
    for(int i = 2 * left + 1; i <= right; i = 2 * i + 1){
        if(i < right && array[i + 1] > array[i]){
            i ++;
        }
        if(target >= array[i]){
            break;
        }
        array[left] = array[i];
        left = i; 
    }
    array[left] = target;
}

public void Swap(int[] array, int i, int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

【演算法解讀】

演算法也是按照先建堆再調整堆的步驟執行的，第一個for回圈，從n / 2 - 1節點開始依次通過呼叫BuildHeap來形成堆，最終完成整個待排序列建堆，第二個for回圈，利用之前已經建好的大頂堆（首元素為最大值），將首元素交換到序列末尾，然后將剩下的元素，再調整堆，再次獲得大頂堆（首元素為次大值），將其首元素交換到倒數第二個位置，以此類推，

演算法的關鍵點在于堆調整BuildHeap方法，該方法調整的節點為left位置的元素（稱其為目標元素），該元素的左右孩子分別是2 * left + 1，2 * left + 2，若目標元素大于等于它的的兩個孩子，則已經是大頂堆，不需要調整了，否則，目標元素和兩個孩子中的較大值交換(對應代碼array[left] = array[i];，即向下滲透)，并將left設定為目標元素交換后所在的位置，重復上述操作，直到目標元素滲透到適當的位置，

【舉個栗子】

對于待排序列1,4,3,2
首先為了便于理解，我們可以將其畫成二叉樹：

轉換方法是將待排序列的元素，從上到下，從左到右，依次填入到二叉樹的節點中，
開始建堆，本例中實際上只需要調整節點1，所以以調整節點1為例：程序如下圖

節點1作為目標元素，先找到其左右孩子（4和3）的較大值4，即比較目標元素1和4,1<4，則交換位置，目標元素1滲透到元素4位置（4被交換到1的位置），在此位置上繼續尋找，其左右孩子，此時只有一個左孩子，元素2，與目標元素做比較，1<2，則1滲透到2的位置，此時目標元素1已經向下滲透到最終位置，建堆成功，序列為4,2,3,1，然后通過大頂堆，得到首元素最大值4，并將其移動到序列尾部，去掉元素4后，再次建堆，重復上述操作，完成排序，

歸并排序

基本思想

所謂歸并是指，把兩個或兩個以上的待排序列合并起來，形成一個新的有序序列，2-路歸并是指，將兩個有序序列合并成為一個有序序列，
2-路歸并排序的基本思想是，對于長度為n的無序序列來說，歸并排序把它看成是由n個只包括一個元素的有序序列組成，然后進行兩兩歸并，最后形成包含n個元素的有序序列
即先將待排序列通過遞回拆解成子序列，然后再對已經排好序的子序列進行合并

復雜度與穩定性與優缺點

• 空間復雜度：O(n)，因為在實作程序中用到了一個臨時序列來暫存歸并程序中的中間結果
• 時間復雜度：O(nlog₂ⁿ)
• 最好情況：O(nlog₂ⁿ)
• 最壞情況：O(nlog₂ⁿ)
• 穩定性：穩定
• 優點：穩定，若采用單鏈表作為存盤結構，可實作就地排序，不需要額外空間
• 缺點：需要O(n)的額外空間

演算法實作

public void MergeSort(int[] array){
    MergeSortImpl(array, 0, array.Length - 1);
}

public void MergeSortImpl(int[] array, int left, int right){
    if(left >= right) return;
    int middle = (left + right) / 2;
    MergeSortImpl(array, left, middle);
    MergeSortImpl(array, middle + 1, right);
    Merge(array, left, middle, right);
}

// 合并兩個子序列
public void Merge(int[] array, int left, int middle, int right){
    int[] temp = new int[right - left + 1];
    int index = 0, lindex = left, rindex = middle + 1;
    while(lindex <= middle && rindex <= right){
        if(array[rindex] < array[lindex]){
            temp[index ++] = array[rindex ++];
        }else{
            temp[index ++] = array[lindex ++];
        }
    }
    while(lindex <= middle){
        temp[index ++] = array[lindex ++];
    }
    while(rindex <= right){
        temp[index ++] = array[rindex ++];
    }

    while(--index >= 0){
        array[left + index] = temp[index];
    }
}

【演算法解讀】

演算法首先通過遞回，不斷將待排序列劃分成兩個子序列，子序列再劃分成兩個子序列，直到每個子序列只含有一個元素（對應代碼：if(left >= right) return;），然后對每對子序列進行合并，合并子序列是通過Merge方法實作，首先定義了一個臨時的輔助空間，長度是兩個子序列之和，然后逐個比較兩個子序列中的元素，元素較小的先放入輔助空間中，若兩個子序列長度不同，則必定有一個子序列有元素未放入輔助空間，因此分別對左邊子序列和右邊子序列中的剩余元素做了處理，最后，兩個子序列的合并結果都存在于輔助空間中，將輔助空間中的有序序列替換到原始序列的對應位置上，

【舉個栗子】

對于待排序列1,4,3,2
第一次遞回，middle = 1，將待排序列分成（1,4），（3,2），繼續對每個子序列劃分子序列，對于序列（1,4,），（3,2），middle都是0，即分別被劃分成（1）（4），（3）（2）直到每個子部分只含有一個元素，然后開始合并，合并（1）（4）得到有序序列（1,4） ，合并（3）（2）得到有序序列（2,3），再次合并（1,4）（2,3），得到最終有序序列（1,2,3,4）

更多

本篇文章演算法的原始碼都放在了GitHub上，感興趣的同學可以點擊這里查看
更多演算法的總結與代碼實作（不僅僅是排序演算法），可以查看GitHub倉庫Algorithm了解

可以發現本篇所匯總的演算法，時間復雜度最低也就是O(nlog₂ⁿ)，包括上一篇匯總講到的交換排序和插入排序也是同樣的結果，其實，基于比較的排序演算法，時間復雜度的下界就是O(nlog₂ⁿ)，下一篇會總結分析可以突破下界O(nlog₂ⁿ)，達到O(n)的排序演算法，敬請期待，

標籤：其他

上一篇：求一個序列中的主元素

下一篇：單鏈表上的基本操作