冒泡排序

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字 的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的 顶端，所以这个算法才被称为“冒泡排序”。

步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

举例

1.对数字 1~9 进行排序

2.在序列的最右边放置一个天平，比较天平两边的数字。如果右边的数字较小，就交换这两个数字的位置。

3.由于 6 < 7，所以交换这两个数字。

4.完成后，天平往左移动一个位置，比较两个数 字的大小。此处 4 < 6，所以无须交换。

5.继续将天平往左移动一个位置并比较数字。重复同样的操作直到天平到达序列最左边为止。

6.不断对数字进行交换，天平最终到达了最左边。通过这一系列操作，序列中最小的数字就会移动到最左边。

7.最左边的数字已经归位。

8.将天平移回最右边，然后重复之前的操作，直到天平到达左边第 2 个位置为止。

9.当天平到达左边第 2 个位置时，序列中第 2 小的数字也就到达了指定位置。

10.将天平再次移回最右边，重复同样的操作直到所有数字都归位为止。

11.由于 9 > 6，所以交换这两个数字。

12.由于 9 > 8，所以交换这两个数字。

13.排序完成

代码

func bubleSort(_ numbers: [Int]) -> [Int] {
    var nums = numbers
    let n = nums.count
    for i in 0..<n {
        for j in 0..<(n-1-i) {
            if nums[j] > nums[j + 1] {
                nums.swapAt(j, j+1)
            }
        }
    }
    return nums
}

let nums = [3, 42, 1, 5, 34, 20, 9]
bubleSort(nums)

性能

在冒泡排序中，第 1 轮需要比较 n-1 次，第 2 轮需要比较 n-2 次......第 n-1 轮需要比较 1 次。因此，总的比较次数为 (n - 1) + (n - 2) + ... + 1 ≈ n^2/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。

不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输入数据正好以从小到大的顺序排列，那么便不需要任何交换操作;反过来，输入数据要是以从大到小的顺序排列，那么每次比较数字后便都要进行交换。因此，冒泡排序的时 间复杂度为 O(n^2)。