02.26 十大經典排序算法（一）

十種常見排序算法可以分為兩大類：

• 比較類排序：通過比較來決定元素間的相對次序，由於其時間複雜度不能突破O(nlogn)，因此也稱為非線性時間比較類排序。
• 非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基於比較排序的時間下界，以線性時間運行，因此也稱為線性時間非比較類排序。

概括一下時間和空間複雜度：

上圖相關概念：

• 穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。
• 不穩定：如果a原本在b的前面，而a=b，排序之後 a 可能會出現在 b 的後面。
• 時間複雜度：對排序數據的總的操作次數。反映當n變化時，操作次數呈現什麼規律。
• 空間複雜度：是指算法在計算機內執行時所需存儲空間的度量，它也是數據規模n的函數。

1 冒泡排序（Bubble Sort）

冒泡排序是一種簡單的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。冒泡排序還有一種優化算法，就是立一個flag，當在一趟序列遍歷中元素沒有發生交換，則證明該序列已經有序。但這種改進對於提升性能來說並沒有什麼太大作用。

算法描述

• 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
• 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
• 針對所有的元素重複以上的步驟，除了最後一個；
• 重複步驟1~3，直到排序完成。

動圖演示

代碼實現

<code>public class BubbleSort implements IArraySort {    @Override    public int[] sort(int[] sourceArray) throws Exception {        // 對 arr 進行拷貝，不改變參數內容        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);        for (int i = 1; i < arr.length; i++) {            // 設定一個標記，若為true，則表示此次循環沒有進行交換，也就是待排序列已經有序，排序已經完成。            boolean flag = true;            for (int j = 0; j < arr.length - i; j++) {                if (arr[j] > arr[j + 1]) {                    int tmp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = tmp;                    flag = false;                }            }            if (flag) {                break;            }        }        return arr;    }}/<code> 

2 選擇排序（Selection Sort）

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

算法描述

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
• 再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
• 重複第二步，直到所有元素均排序完畢。

動圖演示

代碼實現

<code>public class SelectionSort implements IArraySort {    @Override    public int[] sort(int[] sourceArray) throws Exception {        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);        // 總共要經過 N-1 輪比較        for (int i = 0; i < arr.length - 1; i++) {            int min = i;            // 每輪需要比較的次數 N-i            for (int j = i + 1; j < arr.length; j++) {                if (arr[j] < arr[min]) {                    // 記錄目前能找到的最小值元素的下標                    min = j;                }            }            // 將找到的最小值和i位置所在的值進行交換            if (i != min) {                int tmp = arr[i];                arr[i] = arr[min];                arr[min] = tmp;            }        }        return arr;    }}/<code>

3 插入排序（Insertion Sort）

插入排序的代碼實現雖然沒有冒泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

算法描述

• 從第一個元素開始，該元素可以認為已經被排序；
• 取出下一個元素，在已經排序的元素序列中從後向前掃描；
• 如果該元素（已排序）大於新元素，將該元素移到下一位置；
• 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置；
• 將新元素插入到該位置後；
• 重複步驟2~5。

動圖演示

代碼實現

<code>public class InsertSort implements IArraySort {    @Override    public int[] sort(int[] sourceArray) throws Exception {        // 對 arr 進行拷貝，不改變參數內容        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);        // 從下標為1的元素開始選擇合適的位置插入，因為下標為0的只有一個元素，默認是有序的        for (int i = 1; i < arr.length; i++) {            // 記錄要插入的數據            int tmp = arr[i];            // 從已經排序的序列最右邊的開始比較，找到比其小的數            int j = i;            while (j > 0 && tmp < arr[j - 1]) {                arr[j] = arr[j - 1];                j--;            }            // 存在比其小的數，插入            if (j != i) {                arr[j] = tmp;            }        }        return arr;    }}/<code>

4 希爾排序（Shell Sort）

希爾排序按其設計者希爾（Donald Shell）的名字命名，該算法由1959年公佈。

希爾排序，也稱遞減增量排序算法，它是簡單插入排序經過改進之後的一個更高效的版本。實際上，希爾排序就是插入排序的高級版。

希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。它的做法不是每次一個元素挨一個元素的比較。而是初期選用大跨步（增量較大）間隔比較，使記錄跳躍式接近它的排序位置；然後增量縮小；最後增量為 1 ，這樣記錄

簡單插入排序很循規蹈矩，不管數組分佈是怎麼樣的，依然一步一步的對元素進行比較，移動，插入，比如[5,4,3,2,1,0]這種倒序序列，數組末端的0要回到首位置很是費勁，比較和移動元素均需n-1次。而希爾排序在數組中採用跳躍式分組的策略，通過某個增量將數組元素劃分為若干組，然後分組進行插入排序，隨後逐步縮小增量，繼續按組進行插入排序操作，直至增量為1。希爾排序通過這種策略使得整個數組在初始階段達到從宏觀上看基本有序，小的基本在前，大的基本在後。然後縮小增量，到增量為1時，其實多數情況下只需微調即可，不會涉及過多的數據移動。

再舉個例子：

例如，假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應該看起來是這樣：

<code>13 14 94 33 8225 59 94 65 2345 27 73 25 3910/<code>

然後我們對每列進行排序：

<code>10 14 73 25 2313 27 94 33 3925 59 94 65 8245/<code>

將上述四行數字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經移至正確位置了，然後再以3為步長進行排序：

<code>10 14 7325 23 1327 94 3339 25 5994 65 8245/<code>

排序之後變為：

<code>10 14 1325 23 3327 25 5939 65 7345 94 8294/<code>

最後以1步長進行排序（此時就是簡單的插入排序了）。

總結來看：步長是多少，就分多少組（子序列）

算法描述

• 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列個數k，對序列進行k 趟排序；
• 每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

動圖演示

代碼實現

<code>public class ShellSort implements IArraySort {    @Override    public int[] sort(int[] sourceArray) throws Exception {        // 對 arr 進行拷貝，不改變參數內容        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);        int gap = 1;        while (gap < arr.length/3) {            gap = gap * 3 + 1;        }        while (gap > 0) {            for (int i = gap; i < arr.length; i++) {                int tmp = arr[i];                int j = i - gap;                while (j >= 0 && arr[j] > tmp) {                    arr[j + gap] = arr[j];                    j -= gap;                }                arr[j + gap] = tmp;            }            gap = (int) Math.floor(gap / 3);        }        return arr;    }}/<code>

隨著排序的進行，數組越來越接近有序，步長也越來越小，直到gap=1，此時希爾排序就變得跟插入排序一模一樣了，但此時數組已經幾乎完全有序了，對一個幾乎有序的數組運行插入排序，其複雜度接近O(N)。整個過程看起來天衣無縫，然而其中隱藏著一個難點，應該使用怎樣的增量序列？

必須要考慮的因素有兩點：

• 當改變步長的時候，如何保證新的步長不會打亂之前排序的結果？

這不會影響最終排序的正確性，因為只要步長在減小，數組永遠都只會朝著更加有序的方向邁進，但這卻是影響希爾排序效率的關鍵。因為這涉及到完成排序的過程中，算法做了多少無用功。

• 如何保證每一個步長都是有意義的？來看一個例子，假設有一個數組[1,5,2,6,3,7,4,8]，使用步長序列[4,2,1]對其進行排序，過程如圖：

這就相當於進行了一次低效的插入排序，因為在step=1之前，程序什麼也沒幹，偶數位置永遠不會與基數位置進行比較

目前已有的增量算法有以下幾種（ N為數組長度）：

其中第一個它出自Shell本人且非常容易用代碼表達，因此而流行，我看到現在的一些文章中的例子都還在使用它或它的變種。本文中代碼實現部分為了方便演示，選擇了很多例子中慣用的一個增量算法。

希爾排序相對於前面三種排序複雜一些，沒有那麼直觀，需要仔細思考，如果對照程序想不明白，最好Debug一下程序，看一下流程，你會發現其實內核還是插入排序只不過外面套了多個不同步長的子序列，進行了多次插入排序而已。

5 歸併排序（Merge Sort）

歸併排序（MERGE-SORT）是利用歸併的思想實現的排序方法，該算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為2路歸併。

作為一種典型的分而治之思想的算法應用，歸併排序的實現由兩種方法：

• 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
• 自下而上的迭代；

分而治之

可以看到這種結構很像一棵完全二叉樹，本文的歸併排序我們採用遞歸去實現（也可採用迭代的方式去實現）

算法描述

• 把長度為n的輸入序列分成兩個長度為n/2的子序列；
• 對這兩個子序列分別採用歸併排序；
• 將兩個排序好的子序列合併成一個最終的排序序列。

動圖演示

代碼實現

<code>public class MergeSort   {    public int[] sort(int[] sourceArray) throws Exception {        // 對 arr 進行拷貝，不改變參數內容        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);        if (arr.length < 2) {            return arr;        }        int middle = (int) Math.floor(arr.length / 2);        int[] left = Arrays.copyOfRange(arr, 0, middle);        int[] right = Arrays.copyOfRange(arr, middle, arr.length);        return merge(sort(left), sort(right));    }    protected int[] merge(int[] left, int[] right) {        int[] result = new int[left.length + right.length];        int i = 0;        while (left.length > 0 && right.length > 0) {            if (left[0] <= right[0]) {                result[i++] = left[0];                left = Arrays.copyOfRange(left, 1, left.length);            } else {                result[i++] = right[0];                right = Arrays.copyOfRange(right, 1, right.length);            }        }        while (left.length > 0) {            result[i++] = left[0];            left = Arrays.copyOfRange(left, 1, left.length);        }        while (right.length > 0) {            result[i++] = right[0];            right = Arrays.copyOfRange(right, 1, right.length);        }        return result;    }}/<code>

歸併排序是一種穩定的排序方法。和選擇排序一樣，歸併排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是O(nlogn）的時間複雜度。代價是需要額外的內存空間。

關於動畫演示，網上有許多比本文更漂亮的，大家可以搜索看一下，比如 http://sorting.at/ 有多種排序算法的動畫演示，非常漂亮

參考

• https://www.cnblogs.com/onepixel/p/7674659.html
• https://sort.hust.cc/4.shellsort
• https://en.wikipedia.org/wiki/Shellsort
• https://www.cnblogs.com/chengxiao/p/6194356.html
• https://www.kancloud.cn/maliming/leetcode/740190
• https://www.cnblogs.com/chengxiao/p/6104371.html
• https://brilliant.org/wiki/sorting-algorithms/

閱讀更多 小盒子的技術分享 的文章

關鍵字: 比較 FLAG 時間