前言
对于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]为例.
