什么是冒泡排序（Bubble Sort）
首先，我们先瞄一眼冒泡排序算法的定义：
冒泡排序 是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。—— 维基百科
单纯看定义可能比较抽象，没关系，接下来我们将通过一个简单的例子来仔细了解冒泡排序的原理。
举个栗子
假如需要对 1 4 6 2 8 这五个数按照从大到小的排序进行排列，那么我们应该怎么入手解决呢？
首先，比较第 1 位数和第 2 位数的大小。很明显 1 要小于 4，所以我们把 1 和 4 的位置互换一下。
然后，我们继续比较第 2位数和第 3 位数，发现 1 要小于 6，因此把 1 和 6 的位置互换。
继续比较第 3 位和第 4 位数，1 要小于 2，根据要求把 1 和 2 的位置互换。
最后比较第 4 位和第 5 位数，显然 1 小于 8，同理把 1 和 8 的位置互换。
经过这样一轮操作，我们已经不知不觉中把数字 1 的位置放好了，1 是这五个数字中数值最小的，应该排在最后一位。
我们回过头来，看看刚刚才的排序过程，1 的位置经由交换慢慢“浮”到数列的顶端，是不是很像气泡上浮的过程，这也是冒泡排序算法这个名字的由来。
第一轮操作结束后，我们把五个数字中数值最小的 1 摆放好了。第二轮操作我们将会把五个数字中数值第二小的 2 摆放好。仔细想想这个规律，是不是很有意思？同样按照第一轮的规则进行操作，先比较第 1 位和第 2 位数，依此类推，过程如下。
好了，现在还剩下三个数字没摆好，按照这样的规则只要再进行两轮操作就能把剩下三个数字都摆好，没错是两轮，这很容易理解吧。
Swift 3.0 实现
接下来，看一下具体的代码实现：
var numbersArray = [1, 4, 6, 2, 8]
for i in 0...(numbersArray.count - 2) { //n个数进行排序，只要进行（n - 1）轮操作
for j in 0...(numbersArray.count - i - 2){ //开始一轮操作
if numbersArray[j] < numbersArray[j + 1] {
//交换位置
var temp = numbersArray[j]
numbersArray[j] = numbersArray[j + 1]
numbersArray[j + 1] = temp;
}
}
}
print(numbersArray)
时间复杂度分析
最后，我们来计算一下冒泡排序算法的时间复杂度。假设一共有 n 个数字，那么上述第 2 行代码一共执行了 n -1 次循环，第 3 行代码执行了 n - i - 2 次循环
总结
经过上述分析，我们可以看到，冒泡排序的理念十分简单：不断比较相邻的两个元素，如果它们的顺序不符合要求就互相调换。
源代码地址
Github 地址（持续更新中，欢迎 Star）：https://github.com/Zentopia/Algorithm
参考文献
- 啊哈！算法
- 维基百科
网友评论