交换排序算法讲解及swift代码实现

看一种最简单的排序算法（也是性能最低的，也是最好理解的），在这里先称之为“交换排序”。

注意，这个名称是笔者自己起的，在互联网和相关技术书籍上面没有对该算法起名。

算法讲解

用两个循环来嵌套遍历：

• 外层遍历数组从0到末尾的元素，索引为i.
• 里层遍历数组从i+1至数组末尾的元素，索引为j。
• 当i上的元素比j上的元素大的时候，交换i和j的元素，目的是保持index为i的元素是最小的。

我们用一个例子看一下是怎么做交换的：

给定一个初始数组：array = [4, 1, 2, 5, 0]

i = 0 时：

• 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时：

• 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 时：

• array[2] > array[4] : 交换2和4：[0, 1, 2, 5, 4]，i = 2的外层循环结束，i++。

i = 3 时：

• array[3] > array[4] : 交换5和4：[0, 1, 2, 4, 5]，i = 3的外层循环结束，i++。

i = 4 时：不符合内循环的边界条件，不进行内循环，排序结束。

那么用代码如何实现呢？

代码实现

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的函数，在后面会经常用到。

为了用代码验证上面所讲解的交换过程，可以在swapAt函数下面将交换元素后的数组打印出来：

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)
复制代码

打印结果：

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]
复制代码

验证后我们可以看到，结果和上面分析的结果是一样的。

各位读者也可以自己设置原数组，然后在运行代码之前按照自己的理解，把每一次交换的结果写出来，接着和运行算法之后进行对比。该方法对算法的理解很有帮助，推荐大家使用~

请务必理解好上面的逻辑，可以通过动笔写结果的方式来帮助理解和巩固，有助于对下面讲解的排序算法的理解。

大家看上面的交换过程（排序过程）有没有什么问题？相信细致的读者已经看出来了：在原数组中，1和2都是比较靠前的位置，但是经过中间的排序以后，被放在了数组后方，然后再次又交换回来。这显然是比较低效的，给人的感觉像是做了无用功。

那么有没有什么方法可以优化一下交换的过程，让交换后的结果与元素最终在数组的位置基本保持一致呢？