排序系列【比較排序系列之】直接插入排序

最近在和小伙伴們一起研究排序，排序分好多總，后期會做整體總結，本篇則主要對插入排序進行一個整理。
插入排序（insert sorting）的算法思想十分簡單，就是對待排序的記錄逐個進行處理，每個新紀錄與同組那些已排好序的記錄進行比較，然后插入到適當的位置。用三個字總結就是—-“多對一”的關系。
插入排序分好幾種，比如二分插入排序，交換插入排序，直接插入排序，本篇我們重點總結最熟悉的“直接插入排序”。
比如有一個數組【45 34 78 12 34’ 32 29 64】,我們針對此進行一下講解。

排序過程 數組{45 34 78 12 34’ 32 29 64}

第一遍 45和34比較，34<45,所以排序完成為34 45 78 12 34’ 32 29 64

第二遍 78和34 45比較 78>45 78>34,所以位置不變，排序完為 34 45 78 12 34’ 32 29 64

第三遍 12和34 45 78比較 12<78 左移+1，12<45 左移+2，12<34 左移+3，排序完為 12 34 45 78 34’ 32 29 64

第四遍 34’ 左移+2 排序完 12 34 34’ 45 78 32 29 64

第五遍 32 左移+4 排序完 12 32 34 34’ 45 78 29 64

第六遍 29 左移+6 排序完 12 29 32 34 34’ 45 78 64

第七遍 64 左移+1 排序完 12 29 32 34 34’ 45 64 78

用代碼實現的話其實更簡單，引入一個臨時變量，具體看代碼：

 public static void main(String[] args) {Test2 test2 = new Test2();//定義一個數組int[] array = {45, 34, 78, 12, 34, 32 ,29 ,64};test2.insertSort(array);System.out.println(Arrays.toString(array));}void insertSort(int[] array) {//定義的臨時變量int tempRecord;//i從1開始的原因是j=j-1for (int i = 1; i < array.length; i++) {tempRecord = array[i];int j = i - 1;//j不能為負數，根據索引判定值大小，通過臨時變量進行交換while (j >= 0 && tempRecord < array[j]) {array[j + 1] = array[j];j = j - 1;}array[j + 1] = tempRecord;}}

2018年07月30日14:30:55補充：
array[j + 1] = tempRecord，應該放入while循環內，因為若tempRecore不小于array[j]，則此次i循環則直接結束。

通過代碼我們來看一下時間復雜度和空間復雜度。
因為我們只引入了一個輔助存放插入記錄的臨時變量，因此空間代價為一個記錄大小 及O（1）；

當數據正序時，如上我們口述的排序比較過程，執行效率最好，每次插入都不用移動前面的元素，有N個元素參與比較，時間復雜度為O(N)。

當數據反序時，則執行效率最差，每次插入都要前面的元素后移，
i=1時，移動2-1；
i=2時，移動3-1；
當i=n時，移動n-1;
求和公式：n(n-1)/2=O(n2)
所以最壞的時間復雜度為O(N2)