排序算法竞速

四种算法的”风格”

冒泡排序（Bubble Sort）

逐对相邻比较，把大的”冒”到右边。

• 直观：每轮把最大值送到末尾
• 慢：n 个数最坏要 n² 次比较
• 复杂度：$O(n^2)$

插入排序（Insertion Sort）

像整理扑克牌：每次从右边抓一张，往左边已排好的那段里插入正确位置。

• 当数据接近有序时很快
• 复杂度：最坏 $O(n^2)$，最好 $O(n)$

快速排序（Quick Sort）

选一个”基准”，比它小的扔左边，比它大的扔右边，然后两边递归做同样的事。

• 平均 $O(n \log n)$，工业界默认选择
• 最坏（已排序的数组）退化到 $O(n^2)$
• 在演示里看：分得越均匀越快

归并排序（Merge Sort）

把数组对半切，递归排序两半，最后合并两个有序数组。

• 复杂度恒为 $O(n \log n)$
• 需要额外的 $O(n)$ 空间
• 数据库外部排序的常客

为什么差距这么大

n = 80 时：

算法	大致比较次数
冒泡	3200
插入	1600
快排	500
归并	480

n = 10⁶（一百万） 时差距更夸张 —— 冒泡需要一万亿次操作，快排只需两千万次。这就是为什么算法课要讲”复杂度”。

工程现实

实际语言库（Array.prototype.sort、std::sort）用的是混合算法：

• 数据小（< 16 个）→ 插入排序（常数小）
• 数据大 → 快速排序 或 Timsort（归并的改进版）
• 退化时 → 切换到堆排序避免 $O(n^2)$

这套混合策略叫 Introsort（Introspective Sort），Java、C++ STL 都在用。