冒泡排序算法讲解及swift代码现实

2018-09-1015:12:12数据结构与算法Comments3,265 views字数 3923阅读模式

冒泡排序算法讲解

与上面讲的交换排序类似的是，冒泡排序也是用两层的循环来实现的；但与其不同的是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

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

笔者用和上面交换排序使用的同一个数组来演示下元素是如何交换的：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

初始数组：array = [4, 1, 2, 5, 0]文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

i = 0 时：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

array[0] > array[1] : 交换4和1：[1, 4, 2, 5, 0]，内层的j继续遍历，j++。
array[1] > array[2] : 交换4和2：[1, 2, 4, 5, 0]，内层的j继续遍历，j++。
array[2] < array[3] : 不交换，内层的j继续遍历，j++。
array[3] > array[4] : 交换5和0：[1, 2, 4, 0, 5]，i = 0的外层循环结束，i++。

i = 1时：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

array[2] > array[3] : 交换2和4：[1, 2, 0, 4, 5]，内层的j继续遍历，j++。
array[3] < array[4] : 不交换，i = 1的外层循环结束，i++。

i = 2 时：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

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

i = 3 时：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

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

i = 4 时：不符合外层循环的边界条件，不进行外层循环，排序结束。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

代码实现

我们来看一下冒泡排序的代码：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

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

从上面的代码我们可以清楚地看到循环遍历的边界条件和交换时机。同样地，我们添加上log，将冒泡排序每次交换后的数组打印出来（为了进行对比，笔者将交换排序的log也打印了出来）：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.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]

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

从上面两组打印可以看出，冒泡排序算法解决了交换排序算法的不足：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

原来就处于靠前位置的1，2两个元素，在排序的过程中一直是靠前的。
原来处于末尾的0元素，在冒泡排序的过程中一点一点地向前移动，最终到了应该处于的位置。

现在我们知道冒泡排序是好于交换排序的，而且它的做法是相邻元素的两两比较：如果是逆序（左大右小）的话就做交换。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

那么如果在排序过程中，数组已经变成有序的了，那么再进行两两比较就很不划算了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

为了证实上面这个排序算法的局限性，我们用新的测试用例来看一下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

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

而且这次我们不仅仅在交换以后打log，也记录一下作比较的次数：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

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

打印结果：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

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

从打印的结果可以看出，其实在第一次交换过之后，数组已经是有序的了，但是该算法还是继续在比较，做了很多无用功，能不能有个办法可以让这种两两比较在已知有序的情况下提前结束呢？答案是肯定的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

提前结束这个操作很容易，我们只需要跳出最外层的循环就好了。关键是这个时机：我们需要让算法自己知道什么时候数组已经是有序的了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

是否已经想到了呢？就是在一次内循环过后，如果没有发生元素交换，就说明数组已经是有序的，不需要再次缩小内循环的范围继续比较了。所以我们需要在外部设置一个布尔值的变量来标记“该数组是否有序”：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

我们将这个算法称为：advanced bubble sort文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

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

从上面的代码可以看出，在第一个冒泡排序的算法之内，只添加了一个swapped这个布尔值，默认为false：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

如果在当前内循环里面没有发生过元素交换，则说明当前内循环范围的元素都是有序的；那么就说明后续的内循环范围的元素也是有序的（因为内循环每次迭代后都会缩小），就可以跳出循环了。
反之，如果在当前内循环里发生过元素交换，则说明当前内循环很可能是无序的（也可能是有序的，但是有序性需要在下一个内循环中验证，所以还是不能提前退出，还需要进行一次内循环）。

为了验证上面这个改进冒泡排序是否能解决最初给出的冒泡排序的问题，我们添加上对比次数的log：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

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次。之所以没有立即返回，是因为即使在交换完变成有序数组以后，也无法在当前内循环判断出是有序的。需要在下次内循环才能验证出来。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

因为数组的元素数量比较小，所以可能对这个改进所达到的效果体会得不是很明显。现在我们增加一下数组元素的个数，并用记录比较总和的方式来看一下二者的区别：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

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

从比较结果可以看出，这两种算法在该测试样本下的差距是比较大的，而且随着元素个数的增多这个差距会越来越大（因为做了更多没有意义的比较）。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

虽然这种测试样本比较极端，但是在某种意义上还是优化了最初的冒泡排序算法。一般在网上的冒泡排序算法应该都能看到这个优化版的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

现在我们知道这个优化版的冒泡排序算法可以在知道当前数组已经有序的时候提前结束，但是毕竟不断的交换还是比较耗费性能的，有没有什么方法可以只移动一次就能做好当前元素的排序呢？答案又是肯定的，这就引出了笔者即将介绍的选择排序算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4505.html

冒泡排序算法讲解及swift代码现实

冒泡排序算法讲解

代码实现

7个底层数据结构，撑起软件工程的宏伟大厦！

计算机博士：今日头条、抖音推荐算法原理详解

机器学习常用算法精讲：决策树与随机森林

循环神经网络（RNN）基础：如何处理自然语言？

KNN 近邻算法一文读懂，轻松掌握机器学习精髓

马尔科夫链、PCA、贝叶斯太复杂！别怕这有动图图解

10个最常见的机器学习算法介绍 (上)

10个最常见的机器学习算法介绍 (下)

详解遗传算法GA（Python实现代码）

Redis Hash（散列表）实现原理深度图解

Comment