[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作为标尺, 进行扫描, 比其大的排右面, 比其小的排左边, 用递归的方式进行排序而成, 由于一次扫描后同时进行了模糊排序, 效率极高.
