排序算法二：冒泡排序

简化版的桶排序所遗留的问题

严重浪费存储空间

如果排序数的范围是 0~100000 之间，那你则需要申请 100000 个变量，因为我们需要用 100000 个“桶”来存储 0~100000 之间每一个数出现的次数，哪怕你只给5 个数进行排序(例如这 5 个数是 1、300、6000、 8000 和 99999)。假如现在需要排序的不再是整数而是一些小数（例如 5.56789、2.12、1.1、3.123、4.1234，这五个数进行从小到大排序又该怎么办呢）想想是不是疯了。

现在我们来学习另一种新的排序算法:冒泡排序。它可以很好地解决这两个问题。
冒泡排序的基本思想是:每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。

page20image5991424.png

swift 代码如下

func bubbleSort(_ array: inout [Int]) -> [Int] {
    
    for i in 0..<array.count {
        for j in 0..<array.count - 1 - i {
            if array[j] < array[j + 1] {
                let temp = array[j]
                array[j] = array[j+1]
                array[j + 1] = temp
            }
            print(array)
        }
    }
    return array
}

此时输入

8  2  5  3  1  4  6  7  9

排序过程

[8, 2, 5, 3, 1, 4, 6, 7, 9]
[8, 5, 2, 3, 1, 4, 6, 7, 9]
[8, 5, 3, 2, 1, 4, 6, 7, 9]
[8, 5, 3, 2, 1, 4, 6, 7, 9]
[8, 5, 3, 2, 4, 1, 6, 7, 9]
[8, 5, 3, 2, 4, 6, 1, 7, 9]
[8, 5, 3, 2, 4, 6, 7, 1, 9]
[8, 5, 3, 2, 4, 6, 7, 9, 1]
[8, 5, 3, 2, 4, 6, 7, 9, 1]
[8, 5, 3, 2, 4, 6, 7, 9, 1]
[8, 5, 3, 2, 4, 6, 7, 9, 1]
[8, 5, 3, 4, 2, 6, 7, 9, 1]
[8, 5, 3, 4, 6, 2, 7, 9, 1]
[8, 5, 3, 4, 6, 7, 2, 9, 1]
[8, 5, 3, 4, 6, 7, 9, 2, 1]
[8, 5, 3, 4, 6, 7, 9, 2, 1]
[8, 5, 3, 4, 6, 7, 9, 2, 1]
[8, 5, 4, 3, 6, 7, 9, 2, 1]
[8, 5, 4, 6, 3, 7, 9, 2, 1]
[8, 5, 4, 6, 7, 3, 9, 2, 1]
[8, 5, 4, 6, 7, 9, 3, 2, 1]
[8, 5, 4, 6, 7, 9, 3, 2, 1]
[8, 5, 4, 6, 7, 9, 3, 2, 1]
[8, 5, 6, 4, 7, 9, 3, 2, 1]
[8, 5, 6, 7, 4, 9, 3, 2, 1]
[8, 5, 6, 7, 9, 4, 3, 2, 1]
[8, 5, 6, 7, 9, 4, 3, 2, 1]
[8, 6, 5, 7, 9, 4, 3, 2, 1]
[8, 6, 7, 5, 9, 4, 3, 2, 1]
[8, 6, 7, 9, 5, 4, 3, 2, 1]
[8, 6, 7, 9, 5, 4, 3, 2, 1]
[8, 7, 6, 9, 5, 4, 3, 2, 1]
[8, 7, 9, 6, 5, 4, 3, 2, 1]
[8, 7, 9, 6, 5, 4, 3, 2, 1]
[8, 9, 7, 6, 5, 4, 3, 2, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 1]

输出

9  8  7  6  5  4  3  2  1

此时再对代码做点修改，就可解决一遗留的问题了，代码如下

struct Student {
    let name: String
    let score: Int
}

func bubbleSort2(_ array: inout [Student]) -> [Student] {

    for i in 0..<array.count{
        for j in 0..<array.count - 1 - i {
            if array[j].score < array[j + 1].score {
                let temp = array[j]
                array[j] = array[j+1]
                array[j + 1] = temp
            }
        }
    }
    return array
}

可以输入以下数据进行验证

Student(name: "huhu", score: 5)  
Student(name: "haha", score: 3) 
Student(name: "xixi", score: 5)  
Student(name: "hengheng", score: 2)
Student(name: "gaoshou", score: 8)

运行结果是:

Student(name: "gaoshou", score: 8)
 Student(name: "huhu", score: 5)
Student(name: "xixi", score: 5)
Student(name: "haha", score: 3)
Student(name: "hengheng", score: 2)

冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是 O(N^2)。这是一个非常高的时间复杂度。冒泡排序早在 1956 年就有人开始研究，之后有很多人都尝试过对冒泡排序进行改进，但结果却令人失望。如 Donald E. Knuth(中文名为高德纳，1974 年图灵奖获得者)所说:“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外，似乎没有什么值得推荐的。”你可能要问:那还有没有更好的排序算法呢？不要走开，请看下节——快速排序。

参考文献《啊哈！算法》

最后编辑于：2018.01.19 17:17:18