冒泡排序
冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小,再根据结果交换两个数字 的位置”这一操作的算法。在这个过程中,数字会像泡泡一样,慢慢从右往左“浮”到序列的 顶端,所以这个算法才被称为“冒泡排序”。
# 步骤
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
# 举例
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)。