前言
對于iOS開發者來說, 算法的實現過程其實并不怎么關心, 因為只需要調用高級接口就可以得到系統最優的算法, 但了解輪子背后的原理才能更好的取舍, 不是么?下面話不多說了，來一起看看詳細的介紹吧。
選擇排序
我們以[9, 8, 7, 6, 5]舉例.
[9, 8, 7, 6, 5]
第一次掃描, 掃描每一個數, 如比第一個數小則交換, 直到找到最小的數, 將其交換至下標0.
[8, 9, 7, 6, 5][7, 9, 8, 6, 5][6, 9, 8, 7, 5][5, 9, 8, 7, 6]
第二次掃描, 由于確定了第一個數, 則從第二個數開始掃描, 邏輯同上取得次小的數交換至下標1.
[5, 8, 9, 7, 6][5, 7, 9, 8, 6][5, 6, 9, 8, 7]
第三次掃描, 跳過兩個數, 從第三個數開始掃描, 并交換取得下標2.
[5, 6, 8, 9, 7][5, 6, 7, 9, 8]
第四次掃描, 套用上述邏輯取得下標3.
[5, 6, 7, 8, 9]
由于最后只有一位數, 不需要交換, 則無需掃描.
了解了邏輯, 我們來看代碼該怎么寫;
func selectSort(list: inout [Int]) { let n = list.count for i in 0..<(n-1) { var j = i + 1 for _ in j..<n { if list[i] > list[j] { list[i] ^= list[j] list[j] ^= list[i] list[i] ^= list[j] } j += 1 } }}外層循環取從0掃描到n-1, i代表了掃描推進的次數.
內層循環從i+1, 掃描到最后一位, 逐個比較, 如果比i小則交換.
選擇排序(優化)
上述我們通過了非常簡單的邏輯闡述了選擇排序, 果然, 算法沒有想象中難吧. 接下來, 我們來看看如何優化這個排序算法.
我們同樣以[9, 8, 7, 6, 5]舉例.
[9, 8, 7, 6, 5]
第一次掃描, 和之前一樣掃描, 但只記住最小值的下標, 退出內層循環時交換.
[5, 8, 7, 6, 9]
第二次掃描, 確定第一位最小值后推進一格, 邏輯同上進行交換.
[5, 6, 7, 8, 9]
我們可以明顯的看到優化的效果, 交換的次數降低了, 因為我們不是每次交換數值, 而是用指針記錄后跳出內層循環后進行交換.
我們來看下代碼該如何優化:
func optimizationSelectSort(list: inout [Int]) { let n = list.count var idx = 0 for i in 0..<(n - 1) { idx = i; var j = i + 1 for _ in j..<n { if list[idx] > list[j] { idx = j; } j += 1 } if idx != i { list[i] ^= list[idx] list[idx] ^= list[i] list[i] ^= list[idx] } }}通過idx記錄最小值的下標, 如果下標和當前值不等則交換數值.
冒泡排序
接下來我們來看冒泡排序, 同樣以[9, 8, 7, 6, 5]為例.
[9, 8, 7, 6, 5]
第一次掃描, 同樣掃描每一個數, 不同的是, 有兩個指針同時向前走, 如果n>n-1則交換. 確定最末值為最大值.
[8, 9, 7, 6, 5][8, 7, 9, 6, 5][8, 7, 6, 9, 5][8, 7, 6, 5, 9]
第二次掃描, 從頭進行掃描, 由于以確定最末尾為最大值, 則少掃描一位.
[7, 8, 6, 5, 9][7, 6, 8, 5, 9][7, 6, 5, 8, 9]
第三次掃描, 和上述邏輯相同.
[6, 7, 5, 8, 9][6, 5, 7, 8, 9]
第四次掃描, 得到排序完成的值.
[5, 6, 7, 8, 9]
上述可能不好理解, 多看幾遍應該可以.
如果還是理解不能, 我們就來看看代碼吧;
func popSort(list: inout [Int]) { let n = list.count for i in 0..<n-1 { var j = 0 for _ in 0..<(n-1-i) { if list[j] > list[j+1] { list[j] ^= list[j+1] list[j+1] ^= list[j] list[j] ^= list[j+1] } j += 1 } }}外層循環同樣從0掃描到n-1, 這點不贅述.
內層循環從頭也就是0掃描到n-1-i, 也就是每次掃描少掃一位, 應為每次都會確定最末位為最大值.
冒泡排序(優化)
冒泡排序的優化就沒有選擇排序的優化那么給力了, 還有可能產生負優化, 慎用!!
這次我們用[5, 6, 7, 9, 8]來舉例.
--- scope of: popsort ---[5, 6, 7, 9, 8][5, 6, 7, 8, 9]--- scope of: opt_popsort ---[5, 6, 7, 9, 8][5, 6, 7, 8, 9]
這個優化并不是特別直觀, 最好運行我的源碼. 優化來自于如果已經排序完成則不用掃描空轉. 上面的空行就是空轉.
func optimizationPopSort(list: inout [Int]) { let n = list.count for i in 0..<n-1 { var flag = 0 var j = 0 for _ in 0..<(n-1-i) { if list[j] > list[j+1] { list[j] ^= list[j+1] list[j+1] ^= list[j] list[j] ^= list[j+1] flag = 1 } j += 1 } if flag == 0 { break } }}就是加了一個標志位來判斷是否跳出掃描.
快速排序
快速排序, 不是特別好舉例, 但是最重要的一個排序.
func quickSort(list: inout [Int]) { func sort(list: inout [Int], low: Int, high: Int) { if low < high { let pivot = list[low] var l = low; var h = high while l < h { while list[h] >= pivot && l < h {h -= 1} list[l] = list[h] while list[l] <= pivot && l < h {l += 1} list[h] = list[l] } list[h] = pivot sort(list: &list, low: low, high: l-1) sort(list: &list, low: l+1, high: high) } } sort(list: &list, low: 0, high: list.count - 1)}我們直接看代碼就能看出, 我們將下標0作為標尺, 進行掃描, 比其大的排右面, 比其小的排左邊, 用遞歸的方式進行排序而成, 由于一次掃描后同時進行了模糊排序, 效率極高.
排序取舍
我們將上述所有的排序算法和系統的排序進行了比較, 以10000個隨機數為例.
scope(of: "sort", execute: true) { scope(of: "systemsort", execute: true, action: { let list = randomList(10000) timing {_ = list.sorted()}// print(list.sorted()) }) scope(of: "systemsort2", execute: true, action: { let list = randomList(10000) timing {_ = list.sorted {$0 < $1}}// print(list.sorted {$0 < $1}) }) scope(of: "selectsort", execute: true, action: { var list = randomList(10000) timing {selectSort(list: &list)}// print(list) }) scope(of: "opt_selectsort", execute: true, action: { var list = randomList(10000) timing {optimizationSelectSort(list: &list)}// print(list) }) scope(of: "popsort", execute: true, action: { var list = randomList(10000) timing {popSort(list: &list)}// print(list) }) scope(of: "opt_popsort", execute: true, action: { var list = randomList(10000) timing {optimizationPopSort(list: &list)}// print(list) }) scope(of: "quicksort", execute: true, action: { var list = randomList(10000) timing {quickSort(list: &list)}// print(list) })}--- scope of: sort ------ scope of: systemsort ---timing: 0.010432243347168--- scope of: systemsort2 ---timing: 0.00398015975952148--- scope of: selectsort ---timing: 2.67806816101074--- scope of: opt_selectsort ---timing: 0.431572914123535--- scope of: popsort ---timing: 3.39597702026367--- scope of: opt_popsort ---timing: 3.59421491622925--- scope of: quicksort ---timing: 0.00454998016357422
我們可以看到, 其中我寫的快排是效率最高的, 和系統的排序是一個數量級的, 而選擇比冒泡的效率要高, 而令人疑惑的是同樣是系統的排序加上{$0 < $1}比較規則, 效率會有數量級的提升.
現在大家知道如何選擇排序算法了么?
二分搜索
@discardableResult func binSearch(list: [Int], find: Int) -> Int { var low = 0, high = list.count - 1 while low <= high { let mid = (low + high) / 2 if find == list[mid] {return mid} else if (find > list[mid]) {low = mid + 1} else {high = mid - 1} } return -1;}@discardableResult func recursiveBinSearch(list: [Int], find: Int) -> Int { func search(list: [Int], low: Int, high: Int, find: Int) -> Int { if low <= high { let mid = (low + high) / 2 if find == list[mid] {return mid} else if (find > list[mid]) { return search(list: list, low: mid+1, high: high, find: find) } else { return search(list: list, low: low, high: mid-1, find: find) } } return -1; } return search(list: list, low: 0, high: list.count - 1, find: find)}二分搜索的原理就不多說了, 就是折半折半再折半, 這種搜索算法的關鍵就是要有序, 所以配合上合適的排序算法才是最重要的!
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對VEVB武林網的支持。
新聞熱點
疑難解答
