冒泡排序

(图片来自 冒泡排序 - 十大经典排序算法

思路

冒泡排序其实就像「冒泡」,每次迭代都会从头开始,并且将一个最大的数一路冒泡到序列的末尾,因此得名。其算法步骤如下:

  1. 从头到尾遍历一遍,即从比较索引为 [0, 1] 的两个元素开始,到 [1, 2][2, 3]、……、[n - 2, n - 1],每次比较都把较大的数放在后面(通过交换),遍历完第一遍之后,最大的数就会排到序列的末尾,然后我们只需要排剩下的 n - 1 个数。注意这一步的比较中,左边的数的范围是 [0, n - 2]
  2. 不断重复第 1 步,每重复一次,待排序的数的数量就减一;一共重复 $n - 1$ 次。

分析

  • 平均时间复杂度显然为 $O(n^2)$。
  • 最好的情况为该数组已排好序,只需要在第一轮遍历结束的时候增加一个该数组是否需要排序的判断即可,复杂度为 $O(n)$。
  • 最坏的情况为该数组是反序,此时复杂度已经拉满,为 $O(n^2)$。
  • 空间复杂度为 $O(1)$,不需要额外空间。
  • 算法稳定,在对比的时候只有当左数大于右数时才交换,相等时不交换。

实现

见《🔢 排序算法 00. 代码实现》(本博客)。