vlambda博客
学习文章列表

• 属于 比较算法 ^[1]
• 英文简写：BUB

关注、评论、转发

定义

给定一个N个元素的数组，冒泡法排序将：

1. 如果元素大小关系不正确，交换这两个数（在本例中为a> b），
2. 比较一对相邻元素（a，b），
3. 重复步骤1和2，直到我们到达数组的末尾（最后一对是第（N-2）和（N-1）项，因为我们的数组从零开始）
4. 到目前为止，最大的元素将在最后的位置。然后我们将N减少1，并重复步骤1，直到N = 1。

举个例子🌰：[29,10,14,37,14]
第一次冒泡：[10,14,29,14,37]
第二次冒泡：[10,14,14,29,37]

时间复杂度

（标准）Bubble Sort中有两个嵌套循环。外循环正好运行N次迭代。但内部循环运行变得越来越短：

1. 当 i = 0，（N-1）次迭代（比较和可能交换）时。
2. 当 i = 1，（N-2）次迭代时，...
3. 当 i =（N-2）时，1次迭代,
4. 当 i=（N-1），0迭代. 因此，总迭代次数=（N-1）+（N-2）+ ... + 1 + 0 = N *（N-1）/ 2

总时间= c * N *（N-1）/ 2 = O（N^2）

分析

冒泡排序实际上是低效的，它的 时间复杂度为 O(N^2) 。

想象一下，我们有 N = 106 个数字。即使我们的计算机速度超快，并且可以在1秒内计算108次操作，但冒泡排序仍需要大约100秒才能完成。但是，它可以提前终止，例如， 尝试Bubble Sort上面显示的小型升序示例[3,6,11,25,39]，它在O(N)时间结束。改进的思路很简单：如果我们通过内部循环完全不交换，这意味着数组已经排序，我们可以在这个点上停止冒泡排序。

讨论：虽然它使冒泡排序在一般情况下运行得更快，但这种改进的想法并没有改变冒泡排序的 O(N^2) 时间复杂性…为什么？

参考资料