進入到簡單排序的第三個排序，插入排序春弥。其實插入排序呛哟，和冒泡，還有選擇排序都是比較排序算法的一種匿沛，比較效率基本也是O(N2) 但是插入排序扫责，效率基本比冒泡快一倍，選擇快一點逃呼。
有一個已經(jīng)有序的數(shù)據(jù)序列鳖孤，要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序,插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中抡笼，從而得到一個新的苏揣、個數(shù)加一的有序數(shù)據(jù)的數(shù)組，*這里我們可以認為剛開始這個有序數(shù)組其實是為空推姻，那么我們排序就是全排序了*
插入排序的基本思想是：每步將一個待排序的紀錄平匈，按其關鍵碼值的大小插入前面已經(jīng)排序的文件中適當位置上，直到全部插入完為止藏古。
可能不太好理解增炭，我們來看幾個圖
這只是排序的中間狀態(tài)，我們可以假定剛開始數(shù)組有序的部分為空
Paste_Image.png
Paste_Image.png
2.gif
代碼如下
//: MARK - 3 插入排序
func insertionSort<T:Comparable>(aArr:[T]) -> [T] {
var arr = aArr
for outerIndex in 1..<arr.count { // 在插入排序中OuterIndex左側是有序的 拧晕， 右側無需弟跑，依次判斷 并且向右移動給給被標記變量留出位置
let temp = arr[outerIndex] // 標記每次需要被插入的數(shù)據(jù)
var innerIndex = outerIndex
while innerIndex > 0 && arr[innerIndex - 1 ] >= temp { // innerIndex , 遍歷到最左端也就是0結束，或者是遍歷到小于被標記值
arr[innerIndex] = arr[innerIndex - 1 ]
innerIndex -= 1 ; // copy 操作
}
arr[innerIndex] = temp // 插入被標記值
}
return arr
}
print(insertionSort([9,8,7,6,5,4,3,2,1,0]))
// 選法的比較效率 O(N2/4) 比冒泡快一倍防症，比選擇快一點
//對于 基本有序的序列孟辑，由于while循環(huán)總是為假，算法的效率基本達到O(N2) 對于逆序由于復制太多并沒有冒泡快
Paste_Image.png
