插入排序算法和歸併排序算法的分水嶺，你造嗎？

很多情況下，只要跟算法相關的可能都有現成的開源工具包拿來就用，比如排序算法。

現實業務開發時，為了提升效率，確實建議使用現成的成熟的開源工具。

但是，我們如果只知道使用開源工具包的話，如果有一天你去面試被問到的話...

所以，我們應用抽點時間，去學習我們常用的工具包或框架的實現思想和細節。以備急需。

這也就是我們需要不停學習的原因之一吧。

插入排序算法

排序算法場景不用多說了，比如棋牌遊戲中一鍵排序撲克牌，比如電商系統按銷量從高到低排序等等。

排序算法實現有多種，比如插入排序，希爾排序，快速排序，冒泡排序，歸併排序等等。排序算法其實大有講究，每一種算法在不同的輸入規模需要的時間均不一樣。用專業術語來說就是他們的時間複雜度不同。下面我們主要來看一下插入排序和歸併排序的實現原理和不同輸入規模下需要的計算時間。

圖解原理

下面我們通過畫圖+文字方式來講解插入排序原理。先假定某此會議有四個人，會議要求他們坐成一排，且按編號從左邊開始從小到大排列，假定他們到場初始化坐位編號排序為:

現在需要按照會議要求按編號從小到大進行排序，其中一人就提議按照插入排序法方式進行位置的調整，從第二位開始（插入排序法一般從第二項開始）進行，具體如下：

編號5開始調整座位：

編號3調整座位：

編號6調整座位：

可以看到，現在順序變成：

代碼實現

排序算法：

<code>public static void insertSortAsc(Integer[] source) {/<code><code> if (source == null || source.length < 1) {/<code><code> return;/<code><code> }/<code><code> int len = source.length;/<code><code> //i = 1表示從第二項開始，下標從0開始/<code><code> for (int i = 1; i < len; i++) {/<code><code> //當前項/<code><code> int currentVal = source[i];/<code><code> //當前項的前面項最大索引/<code><code> int j = i - 1;/<code><code> //j >= 0表示當前存在哥們，需要繼續詢問/<code><code> //currentVal < source[j]表示詢問你比我大麼？/<code><code> while (j >= 0 && currentVal < source[j]) {/<code><code> //進入這裡表示前面項確實比我大/<code><code> //source[j + 1] = source[j]表示那你往後挪一步/<code><code> source[j + 1] = source[j];/<code><code> //繼續向前詢問/<code><code> j--;/<code><code> }/<code><code> //前面哥們比自己小，或者前面沒有哥們，回退一步回來坐下/<code><code> source[j + 1] = currentVal;/<code><code> }/<code><code>}/<code>

測試：

<code>public static void main(String[] args) {/<code><code>
/<code><code> Integer[] test = {7,5,3,6};/<code><code>
/<code><code> System.out.println("排序前：" + JSON.toJSONString(test));/<code><code> insertSortAsc(test);/<code><code> System.out.println("排序後：" + JSON.toJSONString(test));/<code><code>}/<code>

輸出：

複雜度分析

插入排序算法的時間複雜度範圍為： O(n) - O(n * n)，其中n為輸入項的數量，比如上面輸入項為4項，最好情況下時間複雜度為O(n)。最好情況一般指輸入項本身已經排好順序。最差和平均情況時間複雜度為O(n * n)，最差情況一般指輸入項本身按目標排序反向順序。時間一般指執行所耗費的時間

插入排序算法空間複雜度為O(1)，表示不管輸入項數量大小，運行核心計算所需要的空間相較於其他排序算法來說是固定的，空間一般指內存使用。

歸併排序算法

歸併算法類似二分查找，它遵循分治法範疇，分治法的核心思想是將原問題分解為幾個規模較小但類似於原問題的子問題。然後通過遞歸的方式去求解這些子問題。最後一層一層的合併子問題的解來得到原問題的解。

分治法在每層遞歸一般有以下三個步驟：

分解：分解原問題為若干子問題

求解：遞歸求解子問題

合併：合併子問題的解得到原問題的解

歸併排序算法實現分治法其原理如下：

求解：遞歸排序一分為二的兩個子序列

合併：遞歸合併一分為二已經排好序的序列

文字描述可能太抽象和枯燥，下面我們圖解算法方式講解算法的實現原理

圖解原理

我們複用上面的案例來講解通過歸併算法如何實現會議座位從左到右從小到大排序。

上面待排序項如下：

分解歸併排序如下：

上圖完全展示了歸併算法的核心思想，分解 -> 排序 -> 歸併。就拿5，7，3，6排序來講解，具體步驟如下：

分解：將5，7，3，6大致對半分解為兩組子問題5，7和3，6，繼續將5，7大致按對半分解為兩組5和7。同樣也將3，6按對半分解為3和6兩組子問題，此時對n項輸入分解為6個子問題來處理

求解：從低往上排序，例如7排序後得到7，5排序後得到5，然後進行遞歸合併。

首次歸併將7，5歸併為一組，將3，6歸併為一組。歸併過程進行求解（排序），將7，5排序得到5，7，將3，6排序得到3，6。

繼續歸併將5，7和3，6歸併為5，7，3，6。歸併過程進行求解（排序）所以最後得到3，6，5，7。

合併：由於合併和求解在遞歸過程並行，所以合併操作在求解中已經有所體現。

核心解釋：每次排序是將兩個子問題進行排序，每個子問題實際是放到兩個序列/數組上的，比如7和5這兩個分別放到不同的數組。然後在循環迭代體將這兩個進行比較，把小的放前面，大的放後面保存到另一個數組中。

代碼實現

遞歸按n/2進行分解，當分解為最小子問題時（遞歸到只有一個元素不可再分解時），遞歸開始回升，進入歸併排序，回升一層，歸併排序一層

<code>/**/<code><code> * 通過分治算法實現歸併排序/<code><code> */<code><code> * @param source 需要排序的List/<code><code> * @param beginIndex 開始下標 從0開始，包含開始下標/<code><code> * @param endIndex 結束下標 從0開始， 包含結束下標/<code><code> *//<code><code>public static void mergeSortAsc(List<integer> source, int beginIndex, int endIndex)/<integer> {/<code><code> //當前面一次遞歸只有一個元素時，開始回升當前遞歸/<code><code> if (beginIndex < endIndex) {/<code><code> int subIndex = (beginIndex + endIndex) / 2;/<code><code> //排序左邊段，當遞歸回升後左邊所有已經排好序/<code><code> mergeSortAsc(source, beginIndex, subIndex);/<code><code> //排序右邊段，當遞歸回升後右邊所有已經排好序/<code><code> mergeSortAsc(source, subIndex + 1, endIndex);/<code><code> //合併並排序前面遞歸排好序的兩段/<code><code> doMergeSortAsc(source, beginIndex, subIndex, endIndex);/<code><code> }/<code><code>}/<code>

歸併排序：

<code>private static void doMergeSortAsc(List<integer> source, int beginIndex, int subBeginIndex, int endIndex/<integer>) {/<code><code>
/<code><code> if (SetsUtils.isEmpty(source)) {/<code><code> return;/<code><code> }/<code><code> if (endIndex > source.size()) {/<code><code> throw new RuntimeException("endIndex Not greater than source size");/<code><code> }/<code><code>
/<code><code> int num1 = subBeginIndex - beginIndex + 1;/<code><code> int num2 = endIndex - subBeginIndex;/<code><code>
/<code><code> List<integer> left = SetsUtils.list(num1);/<integer>/<code><code> List<integer> right = SetsUtils.list(num2);/<integer>/<code><code>
/<code><code> for (int i = 0; i < num1; i++) {/<code><code> left.add(source.get(beginIndex + i));/<code><code> }/<code><code> left.add(num1, Integer.MAX_VALUE);/<code><code>
/<code><code> for (int i = 0; i < num2; i++) {/<code><code> right.add(source.get(subBeginIndex + i + 1));/<code><code> }/<code><code> right.add(num2, Integer.MAX_VALUE);/<code><code>
/<code><code>
/<code><code> int i = 0;/<code><code> int j = 0;/<code><code>
/<code><code> for (int k = beginIndex; k <= endIndex; k++) {/<code><code> if (left.get(i) > right.get(j)) {/<code><code> source.set(k, left.get(i));/<code><code> i++;/<code><code> } else {/<code><code> source.set(k, right.get(j));/<code><code> j++;/<code><code> }/<code><code> }/<code><code>}/<code>

測試：

<code>public static void main(String[] args) {/<code><code>
/<code><code> List<integer> test = SetsUtils.list();/<integer>/<code><code> test.add(7);/<code><code> test.add(5);/<code><code> test.add(3);/<code><code> test.add(6);/<code><code>
/<code><code> System.out.println("排序前：" + JSON.toJSONString(test));/<code><code> mergeSortAsc(test, 0, test.size() -1);/<code><code> System.out.println("排序後：" + JSON.toJSONString(test));/<code><code>
/<code><code>}/<code>

輸出：

複雜度分析

歸併排序算法的時間複雜度為： O(nlogn))，其中n為輸入項的數量。時間一般指執行所耗費的時間

歸併排序算法空間複雜度為O(n)，輸入項數量越大，運行核心計算所需要的空間相較於其他排序算法來說越大，空間一般指內存使用。

對比

對比一般需要得出適用場景的結論，一般通過分析時間複雜度和空間複雜度進行定論，很多人喜歡討論時間換空間，空間換時間，這些都是一些術語而已，進一步是要詳細分析計算出算法的具體時間複雜度和空間複雜度，然後得出結論。

我們如何在多種不同的排序算法中選擇一種算法，其實者首先取決於我們的關注的，比如我們的計算機有足夠的空間去浪費，我們需要的是速度，例如電商網站的商品排序。那麼我們就應該分析不同算法的時間複雜度然後進行對比。相反，如果我們更多的關注內存佔用而不關心時間，例如大數據分析的任務調度，那麼我們就應該分析不同算法的空間複雜度然後進行對比。由於時間問題，本篇不詳細計算插入排序和歸併排序的時間複雜度，後面再寫一篇文章進行補充，筆者這裡先給出答案：

1、插入排序法和歸併排序法的時間複雜度對比取決於輸入規模

2、當輸入規模大於1W時歸併排序法優於插入排序法

3、相反，當輸入規模小於1W時，插入排序法優於歸併排序法

4、當輸入規模達到10W以上時，不推薦使用插入排序法

5、當輸入規模達到20W以上時，不推薦使用歸併排序法

對比代碼

<code>public static void main(String[] args) {/<code><code> List<integer> test = SetsUtils.list();/<integer>/<code><code> int i = 10;/<code><code> Random r = new Random();/<code><code> while (i++ < 50000) {/<code><code> test.add(r.nextInt(10000));/<code><code> }/<code><code> List<integer> test1 = new ArrayList<>(test);/<integer>/<code><code> List<integer> test2 = new ArrayList<>(test);/<integer>/<code><code>
/<code><code> long t = System.currentTimeMillis();/<code><code>
/<code><code> System.out.println(JSON.toJSONString(test1));/<code><code> mergeSortAsc(test1, 0, test1.size() - 1);/<code><code> System.out.println(JSON.toJSONString(test1));/<code><code>
/<code><code> long t2 = System.currentTimeMillis();/<code><code>
/<code><code> System.out.println("歸併排序算法耗時：" + (t2 - t) + "ms");/<code><code>
/<code><code> long t3 = System.currentTimeMillis();/<code><code>
/<code><code> System.out.println(JSON.toJSONString(test2));/<code><code> insertSortAsc(test2);/<code><code> System.out.println(JSON.toJSONString(test2));/<code><code>
/<code><code> long t4 = System.currentTimeMillis();/<code><code>
/<code><code> System.out.println("插入排序算法耗時：" + (t4 - t3) + "ms");/<code><code>}/<code>

對比結果