交换排序算法讲解和快速代码实现

我们看一下最简单的排序算法（也是性能最低、最好理解的），这里叫“交换排序”。

注意，这个名字是作者自己起的，网上和相关技术书籍上都没有这个算法的名字。算法矩阵的解释从 i+1 到矩阵末尾的元素，索引 j。

我们用一个例子来看看交换是如何进行的：

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

i = 当

• 时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内层，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, 5i = 外循环结束，我++。

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内置的数组函数来交换两个索引，后面会经常用到。

用代码来验证上面解释的交换过程，可以在函数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)
复制代码

打印结果，我们可以看到： ❝ ，结果是一样的正如上面分析的那样。

读者也可以自己设置原始矩阵，然后在运行代码之前根据自己的理解打印出每次交换的结果，然后与运行算法之后进行比较。这种方法对于理解算法非常有用。推荐大家使用~

请务必理解以上逻辑。你可以通过写出结果来帮助你理解和巩固，这将有助于你理解下面解释的排序算法。

看到上面的切换过程（排序过程）有什么问题吗？我想细心的读者已经猜出来了：在原来的矩阵中，1和2在矩阵中是比较靠前的，但是在中间排序之后，却被放到了矩阵的后面，然后又被交换回来了。这显然是比较无效的，感觉是白费力气。

那么有没有办法优化交换过程，让交换后的结果基本符合数组中元素的最终位置呢？