从冒泡到快排：排序算法怎样悄悄决定你电脑的快慢

你或许从没手写过快排，但你每天都在调用它——数据库 ORDER BY、文件管理器按名称排列、电商按价格筛选，底层都是排序算法。问题是：排序算法差很多吗？答案是：在大数据下，差出成千上万倍。

最朴素的是冒泡排序和插入排序（缺口 B1）：两两比较、逐步归位，最坏要约 n²/2 步。当 n=10^6，这就是约 5×10^11 次操作，普通电脑要算上好几秒甚至更久。但它们的优点是简单、稳定、对基本有序的数据极快（接近 O(n)），所以仍常用于小规模或几乎有序的场景。

真正让排序"起飞"的是 O(n log n) 家族：归并排序（缺口 B2，分治思想）、堆排序（缺口 B4，借助堆结构）、以及日常最常用的快速排序（缺口 B3）。它们把规模砍到对数级，n=10^6 时只需约 2×10^7 步——比冒泡快了两万五千倍。快排之所以"快"，靠的是原地分区：选一个基准，把小的放左、大的放右，再对两边递归，平均 O(n log n) 且常数极小。

那为什么还需要堆排、归并？因为快排在最坏情况（每次都选到最差值）会退化到 O(n²)，工程实现要加随机化基准来规避；而归并排序稳定、堆排最坏也有保证。理解这些取舍，才是"懂算法"而非"会调库"。

排序还是整个算法轨道的钥匙：排好序，才能 O(log n) 二分查找、才能高效去重与区间查询。必学必会已把 B 系列（排序与选择）列为仅次于基础的优先缺口——先让数据"有序"，后面的世界才打得开。

关联推荐

• GPT-5.6 递归自我改进 — 快排本质是递归，看递归思想如何延伸到 AI
• （本批「算法与问题求解入门」KU 发布后回填互链）