Swift中排序算法的簡(jiǎn)單取舍詳解
前言
對(duì)于iOS開(kāi)發(fā)者來(lái)說(shuō), 算法的實(shí)現(xiàn)過(guò)程其實(shí)并不怎么關(guān)心, 因?yàn)橹恍枰{(diào)用高級(jí)接口就可以得到系統(tǒng)最優(yōu)的算法, 但了解輪子背后的原理才能更好的取舍, 不是么?下面話不多說(shuō)了，來(lái)一起看看詳細(xì)的介紹吧。
選擇排序
我們以[9, 8, 7, 6, 5]舉例.
[9, 8, 7, 6, 5]
第一次掃描, 掃描每一個(gè)數(shù), 如比第一個(gè)數(shù)小則交換, 直到找到最小的數(shù), 將其交換至下標(biāo)0.
[8, 9, 7, 6, 5] [7, 9, 8, 6, 5] [6, 9, 8, 7, 5] [5, 9, 8, 7, 6]
第二次掃描, 由于確定了第一個(gè)數(shù), 則從第二個(gè)數(shù)開(kāi)始掃描, 邏輯同上取得次小的數(shù)交換至下標(biāo)1.
[5, 8, 9, 7, 6] [5, 7, 9, 8, 6] [5, 6, 9, 8, 7]
第三次掃描, 跳過(guò)兩個(gè)數(shù), 從第三個(gè)數(shù)開(kāi)始掃描, 并交換取得下標(biāo)2.
[5, 6, 8, 9, 7] [5, 6, 7, 9, 8]
第四次掃描, 套用上述邏輯取得下標(biāo)3.
[5, 6, 7, 8, 9]
由于最后只有一位數(shù), 不需要交換, 則無(wú)需掃描.
了解了邏輯, 我們來(lái)看代碼該怎么寫;
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
}
}
}
外層循環(huán)取從0掃描到n-1, i代表了掃描推進(jìn)的次數(shù).
內(nèi)層循環(huán)從i+1, 掃描到最后一位, 逐個(gè)比較, 如果比i小則交換.
選擇排序(優(yōu)化)
上述我們通過(guò)了非常簡(jiǎn)單的邏輯闡述了選擇排序, 果然, 算法沒(méi)有想象中難吧. 接下來(lái), 我們來(lái)看看如何優(yōu)化這個(gè)排序算法.
我們同樣以[9, 8, 7, 6, 5]舉例.
[9, 8, 7, 6, 5]
第一次掃描, 和之前一樣掃描, 但只記住最小值的下標(biāo), 退出內(nèi)層循環(huán)時(shí)交換.
[5, 8, 7, 6, 9]
第二次掃描, 確定第一位最小值后推進(jìn)一格, 邏輯同上進(jìn)行交換.
[5, 6, 7, 8, 9]
我們可以明顯的看到優(yōu)化的效果, 交換的次數(shù)降低了, 因?yàn)槲覀儾皇敲看谓粨Q數(shù)值, 而是用指針記錄后跳出內(nèi)層循環(huán)后進(jìn)行交換.
我們來(lái)看下代碼該如何優(yōu)化:
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]
}
}
}
通過(guò)idx記錄最小值的下標(biāo), 如果下標(biāo)和當(dāng)前值不等則交換數(shù)值.
冒泡排序
接下來(lái)我們來(lái)看冒泡排序, 同樣以[9, 8, 7, 6, 5]為例.
[9, 8, 7, 6, 5]
第一次掃描, 同樣掃描每一個(gè)數(shù), 不同的是, 有兩個(gè)指針同時(shí)向前走, 如果n>n-1則交換. 確定最末值為最大值.
[8, 9, 7, 6, 5] [8, 7, 9, 6, 5] [8, 7, 6, 9, 5] [8, 7, 6, 5, 9]
第二次掃描, 從頭進(jìn)行掃描, 由于以確定最末尾為最大值, 則少掃描一位.
[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]
上述可能不好理解, 多看幾遍應(yīng)該可以.
如果還是理解不能, 我們就來(lái)看看代碼吧;
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
}
}
}
外層循環(huán)同樣從0掃描到n-1, 這點(diǎn)不贅述.
內(nèi)層循環(huán)從頭也就是0掃描到n-1-i, 也就是每次掃描少掃一位, 應(yīng)為每次都會(huì)確定最末位為最大值.
冒泡排序(優(yōu)化)
冒泡排序的優(yōu)化就沒(méi)有選擇排序的優(yōu)化那么給力了, 還有可能產(chǎn)生負(fù)優(yōu)化, 慎用!!
這次我們用[5, 6, 7, 9, 8]來(lái)舉例.
--- 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]
這個(gè)優(yōu)化并不是特別直觀, 最好運(yùn)行我的源碼. 優(yōu)化來(lái)自于如果已經(jīng)排序完成則不用掃描空轉(zhuǎn). 上面的空行就是空轉(zhuǎn).
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
}
}
}
就是加了一個(gè)標(biāo)志位來(lái)判斷是否跳出掃描.
快速排序
快速排序, 不是特別好舉例, 但是最重要的一個(gè)排序.
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)
}
我們直接看代碼就能看出, 我們將下標(biāo)0作為標(biāo)尺, 進(jìn)行掃描, 比其大的排右面, 比其小的排左邊, 用遞歸的方式進(jìn)行排序而成, 由于一次掃描后同時(shí)進(jìn)行了模糊排序, 效率極高.
排序取舍
我們將上述所有的排序算法和系統(tǒng)的排序進(jìn)行了比較, 以10000個(gè)隨機(jī)數(shù)為例.
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
我們可以看到, 其中我寫的快排是效率最高的, 和系統(tǒng)的排序是一個(gè)數(shù)量級(jí)的, 而選擇比冒泡的效率要高, 而令人疑惑的是同樣是系統(tǒng)的排序加上{$0 < $1}比較規(guī)則, 效率會(huì)有數(shù)量級(jí)的提升.
現(xiàn)在大家知道如何選擇排序算法了么?
二分搜索
@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)
}
二分搜索的原理就不多說(shuō)了, 就是折半折半再折半, 這種搜索算法的關(guān)鍵就是要有序, 所以配合上合適的排序算法才是最重要的!
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)腳本之家的支持。
- 快速排序算法在Swift編程中的幾種代碼實(shí)現(xiàn)示例
- Swift代碼實(shí)現(xiàn)冒泡排序算法的簡(jiǎn)單實(shí)例
- Swift實(shí)現(xiàn)堆排序算法的代碼示例
- Swift實(shí)現(xiàn)快速排序算法的代碼示例
- Swift編程中實(shí)現(xiàn)希爾排序算法的代碼實(shí)例
- 簡(jiǎn)單理解插入排序算法及Swift版的代碼示例
- 理解二叉堆數(shù)據(jù)結(jié)構(gòu)及Swift的堆排序算法實(shí)現(xiàn)示例
- Swift實(shí)現(xiàn)Selection Sort選擇排序算法的實(shí)例講解
相關(guān)文章
Swift在什么情況會(huì)發(fā)生內(nèi)存訪問(wèn)沖突詳解
這篇文章主要給大家介紹了關(guān)于Swift在什么情況會(huì)發(fā)生內(nèi)存訪問(wèn)沖突的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
SwiftUI?引導(dǎo)頁(yè)界面實(shí)現(xiàn)示例
這篇文章主要為大家介紹了SwiftUI?引導(dǎo)頁(yè)界面實(shí)現(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-09-09
這篇文章主要給大家介紹了關(guān)于R.swift使用與安裝的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
Swift?中的?RegexBuilder學(xué)習(xí)指南
這篇文章主要為大家介紹了Swift中的RegexBuilder學(xué)習(xí)指南，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-04-04
這篇文章主要為大家介紹了swift內(nèi)存管理指針類型使用實(shí)例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11
switch語(yǔ)句對(duì)一個(gè)表達(dá)式求值，將結(jié)果與 case 子語(yǔ)句比較，如果匹配，則從 case 處的語(yǔ)句向下執(zhí)行，本文給大家介紹Switch語(yǔ)句的技巧，需要的朋友參考下吧2016-02-02
這篇文章主要介紹了Swift編程中下標(biāo)的用法,是Swift入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-11-11
Swift使用enum抹平數(shù)組元素差異實(shí)例詳解
這篇文章主要為大家介紹了Swift使用enum抹平數(shù)組元素差異實(shí)例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11
Core Image能通過(guò)分析圖片的各個(gè)屬性，人臉的區(qū)域等進(jìn)行自動(dòng)優(yōu)化圖片。我們只需要調(diào)用autoAdjustmentFiltersWithOptions這個(gè)API方法獲取各個(gè)自動(dòng)增強(qiáng)濾鏡來(lái)優(yōu)化圖片即可。不管是人物照片還是風(fēng)景照均可增強(qiáng)效果2015-11-11
委托（代理）是一種設(shè)計(jì)模式，它允許類或結(jié)構(gòu)體將一些需要它們負(fù)責(zé)的功能交由(委托)給其他的類型。下面這篇文章主要介紹了Swift代理模式的相關(guān)資料，文章開(kāi)始先介紹了Objective-C相關(guān)的內(nèi)容，需要的朋友可以參考借鑒，下面來(lái)一起看看吧。2017-03-03