前言
最簡單的排序算法之一是插入排序(insertion sort)。
思路
插入排序的思路是這樣的：
插入排序：由N-1趟排序完成，對于i=1到N-1趟，保證從位置0到位置i上的元素為已排序狀态(但不保證已排序的值一定小于未排序的值)。
過程：
- 對于位置i，先把i位置的值儲存起來，然後把i挖空。
- 依次與前一個位置比較，比較i-1到0位置上的元素；
- 若發現i對應的值小于某個位置的值，則将該位置的值往後移動一位；
- 最後将tmp填入空位
整個過程就是一個不停的往前插的過程，是以叫插入排序
我們對數列：[2, 12, 6, 15, 8] 進行插入排序
其中，i=1和i=3趟都沒發生交換。
代碼
複雜度和穩定性
- 時間複雜度假設被排序的數列中有N個數。周遊一趟的時間複雜度是O(N)，需要周遊多少次呢？N-1次，是以，插入排序的時間複雜度是
- 插入排序穩定性直接插入排序是穩定的算法，它滿足穩定算法的定義。
- 假設在數列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之後，a[i]仍然在a[j]前面。則這個排序算法是穩定的！