看一种最简单的排序算法(也是性能最低的,也是最好理解的),在这里先称之为“交换排序”。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
注意,这个名称是笔者自己起的,在互联网和相关技术书籍上面没有对该算法起名。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
算法讲解
用两个循环来嵌套遍历:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
- 外层遍历数组从0到末尾的元素,索引为i.
- 里层遍历数组从i+1至数组末尾的元素,索引为j。
- 当i上的元素比j上的元素大的时候,交换i和j的元素,目的是保持index为i的元素是最小的。
我们用一个例子看一下是怎么做交换的:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
给定一个初始数组:array = [4, 1, 2, 5, 0]
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
i = 0 时:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
- array[0] > array[1] : 交换4和1:
[1, 4, 2, 5, 0]
,内层的j继续遍历,j++。 - array[0] > array[4] : 交换0和1:
[0, 4, 2, 5, 1]
,i = 0的外层循环结束,i++。
i = 1时:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
- array[1] > array[2] : 交换2和4:
[0, 2, 4, 5, 1]
,内层的j继续遍历,j++。 - array[1] > array[4] : 交换1和2:
[0, 1, 4, 5, 2]
,i = 1的外层循环结束,i++。
i = 2 时:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
- array[2] > array[4] : 交换2和4:
[0, 1, 2, 5, 4]
,i = 2的外层循环结束,i++。
i = 3 时:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
- array[3] > array[4] : 交换5和4:
[0, 1, 2, 4, 5]
,i = 3的外层循环结束,i++。
i = 4 时:不符合内循环的边界条件,不进行内循环,排序结束。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
那么用代码如何实现呢?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
代码实现
func switchSort(_ array: inout [Int]) -> [Int] {
guard array.count > 1 else { return array }
for i in 0 ..< array.count {
for j in i + 1 ..< array.count {
if array[i] > array[j] {
array.swapAt(i, j)
}
}
}
return array
}
复制代码
这里面swapAt
函数是使用了Swift内置的数组内部交换两个index的函数,在后面会经常用到。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
为了用代码验证上面所讲解的交换过程,可以在swapAt
函数下面将交换元素后的数组打印出来:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
var originalArray = [4,1,2,5,0]
print("original array:\n\(originalArray)\n")
func switchSort(_ array: inout [Int]) -> [Int] {
guard array.count > 1 else { return array }
for i in 0 ..< array.count {
for j in i + 1 ..< array.count {
if array[i] > array[j] {
array.swapAt(i, j)
print("\(array)")
}
}
}
return array
}
switchSort(&originalArray)
复制代码
打印结果:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
original array:
[4, 1, 2, 5, 0]
switch sort...
[1, 4, 2, 5, 0]
[0, 4, 2, 5, 1]
[0, 2, 4, 5, 1]
[0, 1, 4, 5, 2]
[0, 1, 2, 5, 4]
[0, 1, 2, 4, 5]
复制代码
验证后我们可以看到,结果和上面分析的结果是一样的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
各位读者也可以自己设置原数组,然后在运行代码之前按照自己的理解,把每一次交换的结果写出来,接着和运行算法之后进行对比。该方法对算法的理解很有帮助,推荐大家使用~文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
请务必理解好上面的逻辑,可以通过动笔写结果的方式来帮助理解和巩固,有助于对下面讲解的排序算法的理解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
大家看上面的交换过程(排序过程)有没有什么问题?相信细致的读者已经看出来了:在原数组中,1和2都是比较靠前的位置,但是经过中间的排序以后,被放在了数组后方,然后再次又交换回来。这显然是比较低效的,给人的感觉像是做了无用功。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html
那么有没有什么方法可以优化一下交换的过程,让交换后的结果与元素最终在数组的位置基本保持一致呢?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4504.html