《程序兵法： Java 源碼的插入排序算法 （二）》
文章工程：
- JDK 1.8
- 工程名：algorithm-core-learning
- 工程地址：https://github.com/JeffLi1993/algorithm-core-learning
一、前言
上一講《程序兵法：Java String 源碼的排序算法（一）》講了什么是選擇問題，什么是比較能力。
選擇問題，是假設一組 N 個數，要確定其中第 K 個最大值者。算法是為求解一個問題。
那什么是算法？
算法是某種集合，是簡單指令的集合，是被指定的簡單指令集合。確定該算法重要的指標：
- 第一是否能解決問題；
- 第二算法運行時間，即解決問題出結果需要多少時間；
- 還有所需的空間資源，比如內存等。
很多時候，寫一個工作程序并不夠。因為遇到大數據下，運行時間就是一個重要的問題。
算法性能用大 O 標記法表示。大 O 標記法是標記相對增長率，精度是粗糙的。比如 2N 和 3N + 2 ，都是 O(N)。也就是常說的線性增長，還有常說的指數增長等
典型的增長率
典型的提供性能做法是分治法，即分支 divide and conquer 策略：
- 將問題分成兩個大致相等的子問題，遞歸地對它們求解，這是分的部分；
- 治階段將兩個子問題的解修補到一起，并可能再做些少量的附加工作，最后得到整個問題的解。
二、排序
排序問題，是古老，但一直流行的問題。從 ACM 接觸到現(xiàn)在工作，每次涉及算法，或品讀 JDK 源碼中一些算法，經常會有排序的算法出現(xiàn)。
排序算法是為了將一組數組（或序列）重新排列，排列后數據符合從大到?。ɑ驈男〉酱螅┑拇涡颉＿@樣數據從無序到有序，會有什么好處？
- 應用層面：解決問題。
- 最簡單的是可以找到最大值或者最小值
- 解決"一起性"問題，即相同標志元素連在一起
- 匹配在兩個或者更多個文件中的項目
- 通過鍵碼值查找信息
- 系統(tǒng)層面：減少系統(tǒng)的熵值，增加系統(tǒng)的有序度
（Donald Knuth 的經典之作《計算機程序設計藝術》(The Art of Computer Programming)的第三卷）
通過維基百科查閱資料得到：
在主內存中完成的排序叫做，內部排序。那需要在磁盤等其他存儲完成的排序，叫做外部排序 external sorting。資料地址：https://en.wikipedia.org/wiki/External_sorting
上一篇《程序兵法：Java String 源碼的排序算法（一）》，講到了 java.lang.Comparable 接口。那么接口是一個抽象類型，是抽象方法（compareTo）的集合，用 interface 來聲明。因此被排序的對象屬于 Comparable 類型，即實現(xiàn) Comparable 接口，然后調用對象實現(xiàn)的 compareTo 方法進行比較后排序。
在這些條件下的排序，叫作基于比較的排序（comparison-based sorting）
三、插入排序
白話文：熊大（一）、熊二、熊三... 按照身高從低到高排隊（排序）。這時候熊 N 加入隊伍，它從隊伍尾巴開始比較。如果它比前面的熊身高低，則與被比較的交換位置，依次從尾巴到頭部進行比較 & 交換位置。最終換到了應該熊 N 所在的位置。這就是插入排序的原理。
插入排序（insertion sort）
- 最簡單的排序之一。ps: 冒泡排序看看就好，不推薦學習
- 由 N - 1 次排序過程組成。
- 如果被排序的這樣一個元素，就不需要排序。即 N =1 （1 - 1 = 0）
- 每一次排序保證，從第一個位置到當前位置的元素為已排序狀態(tài)。
- 如圖：每個元素往前進行比較，并終止于自己所在的位置
/**
* 插入排序案例
* <p>
* Created by 泥瓦匠@bysocket.com on 19/5/15.
*/
public class InsertionSortingDemo {
/**
* 插入排序
*
* @param arr 能比較的對象數組
* @param <T> 已排序的對象數組
*/
public static <T extends Comparable> void insertionSort(T[] arr) {
int j;
// 從數組第二個元素開始，向前比較
for (int p = 1; p < arr.length; p++) {
T tmp = arr[p];
// 循環(huán)，向前依次比較
// 如果比前面元素小，交換位置
for (j = p; (j > 0) && (tmp.compareTo(arr[j - 1]) < 0); j--) {
arr[j] = arr[j - 1];
}
// 如果比前面元素大或者相等，那么這就是元素的位置，交換
arr[j] = tmp;
}
}
public static void main(String[] args) {
Integer[] intArr = new Integer[] {2, 3, 1, 4, 3};
System.out.println(Arrays.toString(intArr));
insertionSort(intArr);
System.out.println(Arrays.toString(intArr));
}
}
代碼解析如下：
- 從數組的第二個元素，向前開始比較。比第一個元素小，則交換位置
- 如果第二個元素比較完畢，那就第三個，第四個... 以此類推
- 比較到最后一個元素時，完成排序
時間復雜度是 O(N^2)，最好情景的是排序已經排好的，那就是 O（N），因為滿足不了循環(huán)的判斷條件；最極端的是反序的數組，那就是 O(N^2)。所以該算法的時間復雜度為 O(N^2)
運行 main 方法，結果如下：
[2, 3, 1, 4, 3]
[1, 2, 3, 3, 4]
再考慮考慮優(yōu)化，會怎么優(yōu)化呢？
插入排序優(yōu)化版 不是往前比較 。往前的一半比較，二分比較會更好。具體代碼，可以自行試試
四、Array.sort 源碼中的插入排序
上面用自己實現(xiàn)的插入算法進行排序，其實 JDK 提供了 Array.sort 方法，方便排序。案例代碼如下：
/**
* Arrays.sort 排序案例
* <p>
* Created by 泥瓦匠@bysocket.com on 19/5/28.
*/
public class ArraysSortDemo {
public static void main(String[] args) {
Integer[] intArr = new Integer[] {2, 3, 1, 4, 3};
System.out.println(Arrays.toString(intArr));
Arrays.sort(intArr);
System.out.println(Arrays.toString(intArr));
}
}
運行 main 方法，結果如下：
[2, 3, 1, 4, 3]
[1, 2, 3, 3, 4]
那 Arrays.sort 是如何實現(xiàn)的呢？JDK 1.2 的時候有了 Arrays ，JDK 1.8 時優(yōu)化了一版 sort 算法。大致如下：
- 如果元素數量小于 47，使用插入排序
- 如果元素數量小于 286，使用快速排序
- Timsort 算法整合了歸并排序和插入排序
源碼中我們看到了 mergeSort 里面整合了插入排序算法，跟上面實現(xiàn)的異曲同工。這邊就不一行一行解釋了。
五、小結
算法是解決問題的。所以不一定一個算法解決一個問題，可能多個算法一起解決一個問題。達到問題的最優(yōu)解。插入排序，這樣就這么簡單
資料：
- 《數據結構與算法分析：Java語言描述（原書第3版）》
- https://www.cnblogs.com/vamei/tag/%E7%AE%97%E6%B3%95/
