冒泡排序

冒泡排序

• 时间复杂度：最好 $O(n)$，最坏 $O(n^2)$
• 可能优化
  • 提前终止：某次迭代中没有进行交换，说明前缀已经有序，直接跳出循环
  • 跳跃：在前一次扫描中，若最后被交换的是 $[last-1]$ 和 $[last]$，则 $[last,hi)$ 已经有序，可以跳过这个后缀
• 可以实现稳定性，输入序列中相等元素在输出序列中的相对位置不变
• 每次交换相邻的逆序对不一定减少，但总逆序对一定减少