Day 07：泡沫排序(bubble sort)

如果一个阵列中的任两个元素是有排序的，是不是代表整个阵列就是排序好的？
这就是泡沫排序的想法。

如果我们想将一列数字由小到大排好，用泡沫排序的步骤是：

1. 两个相邻的数字相比，如果第二个比第一个小，两个数字交换。
2. 从头到尾任两个数字都进行同样操作，最後一个数字排序完成。
3. 除了最後一个数字外，再从头开始进行相邻数字比较。
4. 重复上述步骤直到所有数字都排序好。

举例来说：
3, 6, 2, 7, 1, 4, 5
// 首先3, 6相比，不交换

3, 6, 2, 7, 1, 4, 5
// 6, 2相比，交换

3, 2, 6, 7, 1, 4, 5
// 6, 7 相比，不交换

3, 2, 6, 7, 1, 4, 5
// 7, 1 相比，交换

3, 2, 6, 1, 7, 4, 5
// 7, 4 相比，交换

3, 2, 6, 1, 4, 7, 5
// 7, 5 相比，交换

3, 2, 6, 1, 4, 5, 7
// 一轮比完後，最大的数字7会换到最後一个位置

可以看到在比较的过程，最大的数字碰到任何数字都会被往後交换，视觉上就像泡泡一样浮到阵列的最末尾，所以才有泡沫排序这个名称。如此一来，最後一个数字就算排序完成，所以下一轮的比较就不需要再操作最後一个数字。

泡沫排序跟选择排序一样，一次排好一个数字，每一轮要经过逐一比较才完成，所以它的执行时间一样也是O(n²)。

正常来说，泡沫排序在最佳情况也会把所有元素比较一遍，不过如果是操作有序阵列，过程中不会有任何元素交换，所以我们可以增加一个条件，「如果没有任何元素交换，排序结束」，这样可以让泡沫排序比较一遍就结束，等於最佳情况执行时间可以降到Ω(n)。

泡沫排序还有其他的变形，例如鸡尾酒排序(cocktail shaker sort)。鸡尾酒排序的特点是排序是双向的，也就是会从第一个元素开始比较相邻元素、排好末尾的数字，再从阵列末尾比较回来、排好第一个数字。以下是鸡尾酒排序的示意图：

图片来源：维基百科

虽然这样的双向排序好像增进了一点点效能，它的平均执行时间仍然要O(n²)。整体来说，泡沫排序和鸡尾酒排序等变化型仍然都算是非常慢的演算法。

接下来会写到一些手法不同、效率更高的演算法。