冒泡排序算法解释和 Swift 代码现实

terry 2年前 (2023-09-27) 阅读数 63 #数据结构与算法

冒泡排序算法解释

与上面的交换排序类似，冒泡排序也是使用两级循环实现的；但不同的是：

循环边界条件：冒泡排序的外层是[0, array.count-1)；内层是[0, array.count-1-i)。可以看到，内层的射程不断减小，射程前端保持不变，后端向前移动。
交换排序比较内部索引和外部索引（array[i] 和 array[j]）的元素，但冒泡排序比较两个相邻内部索引的元素：array[j] 和 array[j+1]。

作者使用上面交换排序中使用的相同数组来演示如何交换元素：

初始数组：array = [4, 1, 2, 5, 0]

i = 0时间：

field[0] > field[1]：交换4和1：[1,4,2,5,0]，内心诗句，j继续前进。
array[1] > array[2]：交换4和2：[1, 2, 4, 5, 0]，内层j继续过渡，j++。
array[2]
field[3] > field[4] ：交换 5 和 0：[1, 2, 4, 0, 5]，i = 0 的外循环结束，i++。当

i = 1 时：

array[2] > array[3]：交换 2 和 4：[1, 2, 0, 4, 5]，内层继续遍历，j++。
array[3]

i = 2时，：

array[1] > array[2]：交换2和0：[1, 0, 2, 4, 5][1, 0 , 2, 4, 5] j继续遍历，j++，直到退出外循环i=2，i++。当

i = 3时，：

array[0] > array[1]：交换1和0：[0, 1, 2, 4, 5] j继续遍历，j++，直到退出外循环i=3，i++。当

i = 4时：不满足外循环边界条件，不执行外循环，排序结束。

代码实现

我们看一下冒泡排序代码：

func bubbleSort(_ array: inout [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }
    
    for i in 0 ..< array.count - 1 {

        for j in 0 ..< array.count - 1 - i {
          
            if array[j] > array[j+1] {
                array.swapAt(j, j+1)                 
            }
        }
    }
    return array
}
复制代码

从上面的代码中，我们可以清楚地看到循环过渡的边界条件和交换时机。同样，我们在每次冒泡排序交换后添加一条日志并打印数组（为了对比，作者还打印了交换排序日志）：

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]

bubble sort...
[1, 4, 2, 5, 0]
[1, 2, 4, 5, 0]
[1, 2, 4, 0, 5]
[1, 2, 0, 4, 5]
[1, 0, 2, 4, 5]
[0, 1, 2, 4, 5]
复制代码

从上面两组抑制可以看出，冒泡排序的冒泡排序算法解决了交换排序算法的缺点：

原本排在前面的两个元素1和2在排序过程中始终排在前面。原本位于最后的
元素0在冒泡排序的过程中一点点向前移动，最终到达了它应该所在的位置。

现在我们知道冒泡排序比库存排序更好，它的做法是两两比较相邻元素：如果顺序相反（左大，右小），那么就会交换。

因此，如果在排序过程中对数组进行了排序，那么执行两两比较并不划算。

为了确认上面的排序算法的局限性，我们来看一个新的测试用例：

var originalArray = [2,1,3,4,5]
复制代码

而这次，交换之后，我们不仅会登录，还会记录比较的次数：

func bubbleSort(_ array: inout [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }    
    var compareCount = 0
    
    for i in 0 ..< array.count - 1 {

        for j in 0 ..< array.count - 1 - i {

            compareCount += 1
            print("No.\(compareCount) compare \(array[j]) and \(array[j+1])")
            
            if array[j] > array[j+1] {
                array.swapAt(j, j+1) //keeping index of j is the smaller one
                print("after swap: \(array)")
                
            }
        }
    }
    return array
}
复制代码

打印结果：

original array:
[2, 1, 3, 4, 5]


bubble sort...
No.1 compare 2 and 1
after swap: [1, 2, 3, 4, 5] //already sorted, but keep comparing
No.2 compare 2 and 3
No.3 compare 3 and 4
No.4 compare 4 and 5
No.5 compare 1 and 2
No.6 compare 2 and 3
No.7 compare 3 and 4
No.8 compare 1 and 2
No.9 compare 2 and 3
No.10 compare 1 and 2
复制代码

从打印的结果可以看出，其实第一次交换后，数组已经没问题了，但是算法还在继续比较，做了很多不必要的工作。有没有办法做到这一点？如果在已知顺序的情况下这种成对比较提前结束怎么办？答案是肯定的。

提前结束这个操作很容易，我们只需跳出最外层循环即可。关键是这个时机：当数组已经排序

时，我们需要让算法知道。
你想好了吗？这意味着，如果内循环之后没有交换元素，则说明数组已经没问题了，不需要再次缩小内循环的范围来继续比较。所以我们需要在外部设置一个布尔变量来表示“数组是否已排序”：
我们称这个算法为：高级冒泡排序
func bubbleSortAdvanced(_ array: inout [Int]) -> [Int] { guard array.count > 1 else { return array } for i in 0 ..< array.count - 1 { //bool switch var swapped = false for j in 0 ..< array.count - i - 1 { if array[j] > array [j+1] { array.swapAt(j, j+1) swapped = true; } } //if there is no swapping in inner loop, it means the the part looped is already sorted, //so it's time to break if (swapped == false){ break } } return array } 复制代码
从上面的代码可以看出，在第一个风险内冒泡排序算法中，只有一个交换了是一个附加的布尔值。默认为 false：
如果当前内循环没有发生元素交换，则表示当前内循环范围内所有元素都没有问题；那么这意味着内部循环的下一个范围中的元素也很好（因为每次迭代后内部循环都会变小），并且您可以跳出循环。
相反，如果当前内循环中的元素已经交换过，则说明当前内循环很可能是乱序的（也可以是有序的，但需要在下一个内循环中验证顺序），所以它仍然不能提前终止需要内部循环）。
为了检验上面改进的冒泡排序能否解决原来给定的冒泡排序问题，我们添加比较次数的log：
original array: [2, 1, 3, 4, 5] bubble sort... No.1 compare 2 and 1 after swap: [1, 2, 3, 4, 5] No.2 compare 2 and 3 No.3 compare 3 and 4 No.4 compare 4 and 5 No.5 compare 1 and 2 No.6 compare 2 and 3 No.7 compare 3 and 4 No.8 compare 1 and 2 No.9 compare 2 and 3 No.10 compare 1 and 2 bubble sort time duration : 1.96ms advanced bubble sort... No.1 compare 2 and 1 after swap: [1, 2, 3, 4, 5] No.2 compare 2 and 3 No.3 compare 3 and 4 No.4 compare 4 and 5 No.5 compare 1 and 2 No.6 compare 2 and 3 No.7 compare 3 and 4 复制代码
我们可以看到，使用改进的冒泡排序后，比较次数减少了3倍。之所以没有立即返回，是因为即使交换完成，成为有序数组后，也无法判断在当前内循环中是否是有序的。需要在下一个内循环中进行验证。
由于数组的元素数量比较少，所以这个改进的效果可能不是很明显。现在我们增加数组元素个数，用记录来比较
的和，看看两者的区别：

original array:
[2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

bubble sort...
total compare count： 91


advanced bubble sort...
total compare count： 25
复制代码

从比较结果可以看出，这两种算法的性能根据对于这个测试样本gap比较大，并且随着元素数量的增加，gap会越来越大（因为进行了更多无意义的比较）。

这个测试样例虽然比较极端，但某种意义上还是优化了原来的冒泡排序算法。一般来说，你应该能够在互联网上看到这个优化版本的冒泡排序算法。

现在我们知道，这个优化版本的冒泡排序算法在知道当前数组没问题的情况下可以更早完成，但毕竟不断交换仍然是相对性能密集型的。有什么办法可以一次性做到这一点吗？目前的元素安排如何？同样，答案是肯定的，这引出了作者稍后将介绍的选择排序算法。