進入到簡單排序的第三個排序，插入排序。其實插入排序，和冒泡，還有選擇排序都是比較排序算法的一種，比較效率基本也是O(N2) 但是插入排序，效率基本比冒泡快一倍，選擇快一點。 有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據的數組，*這里我們可以認為剛開始這個有序數組其實是為空，那么我們排序就是全排序了* 插入排序的基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。

可能不太好理解，我們來看幾個圖

這只是排序的中間狀態，我們可以假定剛開始數組有序的部分為空

---

代碼如下

//: MARK - 3 插入排序 func insertionSort<T:Comparable>(aArr:[T]) -> [T] { 復制代碼

var arr = aArr ? ? for outerIndex in 1..<arr.count { //? 在插入排序中OuterIndex左側是有序的 ， 右側無需，依次判斷 并且向右移動給給被標記變量留出位置 ?? ? ? let temp = arr[outerIndex] // 標記每次需要被插入的數據 ? ? ? ? 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循環總是為假，算法的效率基本達到O(N2) 對于逆序由于復制太多并沒有冒泡快 復制代碼

總結

以上是生活随笔為你收集整理的iOS程序员也要学点算法吧 简单排序之插入排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。