工作原理
排序就是把元素排成顺序——从小到大、从 A 到 Z。下面所有算法解决的是同一个问题,区别只在策略, 而你看的正是策略。选一种算法(或竞速模式一次看六种),选一份输入,按下播放。引擎工作时 条形会亮起:黄色表示比较,红色表示移动或交换,紫色表示 主元,绿色表示已就位。
控件像视频播放器,因为引擎本身就是:空格播放/暂停,右箭头单步,R 重来,N 生成新列表,S 打乱,速度从 0.25× 到 8×。代码面板会随着执行高亮每一行伪代码,动画和程序保持同步。把同一场 竞速跑两遍:一次逆序列表,一次近乎有序,看插入排序从队尾跳到前列。
六种算法
其中三种是简单的平方级方法——好写,大规模下很痛;三种是高效方法,用分治 或巧妙的数据结构达到 O(n log n)。下面每个例子都是完整可运行的 Python,操作普通列表。
冒泡排序 — 相邻交换
逐个比较相邻元素,逆序就交换。每走完一遍,最大的未排序元素就“冒泡”到最终位置,下一遍就可以少走一步。 如果完整一遍没有任何交换,说明列表已有序,算法提前停止——这是它唯一的优点,也是已经有序的输入下达到 O(n) 的原因。
def bubble_sort(a):
n = len(a)
for end in range(n - 1, 0, -1):
swapped = False
for i in range(end):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
if not swapped:
break
return a选择排序 — 反复挑最小
把列表分成已排序的前部和未排序的其余部分。每一步扫描整个未排序部分找出最小值,换到应有的位置。无论输入 本来多有序,它做的比较次数都一样——约 n²/2,所以最好、平均、最坏都是 O(n²)。它的优点是最多只做 n 次交换, 在交换很昂贵的年代这很有用。
def selection_sort(a):
n = len(a)
for i in range(n):
m = i
for j in range(i + 1, n):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i]
return a插入排序 — 扑克牌手的方法
就像手里理扑克牌:拿起下一张,向左滑过所有更大的牌,直到放好。在近乎有序的数据上几乎不用动,所以是 O(n)—— 这种情况全场最快,也是真实混合排序在小子列表里用它的原因。在逆序数据上每张牌都要走完全程:最坏 O(n²)。 它稳定,不用额外内存。
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a归并排序 — 分而治之再归并
把列表对半分,每半用同样方法排序(递归到底是单个元素,按定义已有序),再每次取两边队首较小者归并起来。 划分永远均衡,所以每层代价 O(n),共 log n 层:所有情况都保证 O(n log n)。代价是归并需要 O(n) 额外内存; 它稳定——相等元素永不交叉。
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]快速排序 — 按主元划分
选一个主元做划分:小的放左边,大的放右边,两边同样处理。主元落在中间附近时,递归 log n 层,总计 O(n log n),常数极小,只需 O(log n) 的额外内存用于递归——实践中通常最快。主元落在极端时,一边几乎装下全部,退化到 O(n²)。本模拟器用三数取中选主元(首、中、尾),真实数据中坏情况很少见。下面的 Python 示例为了简短,直接用最后一个元素作主元。
def quick_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo < hi:
p, i = a[hi], lo
for j in range(lo, hi):
if a[j] < p:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
quick_sort(a, lo, i - 1)
quick_sort(a, i + 1, hi)
return a堆排序 — 伪装的优先队列
把列表变成大顶堆:压进数组的二叉树,每个父亲都大于孩子,所以最大值总在零号位。反复取出 最大值换到末尾,堆缩小一位,再把新堆顶下沉恢复性质。保证 O(n log n),额外内存 O(1)——但跳跃的访问模式不 受处理器缓存待见,计时上常输给快速和归并排序,纸面上却是平手。
def heap_sort(a):
def sift(lo, n, i):
while True:
l, r, m = 2 * i + 1, 2 * i + 2, i
if l < n and a[lo + l] > a[lo + m]:
m = l
if r < n and a[lo + r] > a[lo + m]:
m = r
if m == i:
return
a[lo + i], a[lo + m] = a[lo + m], a[lo + i]
i = m
n = len(a)
for i in range(n // 2 - 1, -1, -1):
sift(0, n, i)
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift(0, end, 0)
return a读懂表格
大 O 描述的是增长,不是秒表:有意忽略常数和硬件,让扩展的形状显现。下表是标准参考(Cormen 等,Introduction to Algorithms;NIST 算法与数据结构词典)。“稳定”指相等元素保持原来的顺序。
| 算法 | 最好 | 平均 | 最坏 | 额外空间 | 稳定 |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | 是 |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | 否 |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | 是 |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | 否 |
在模拟器里试试:让六种算法先跑逆序列表,再跑近乎有序列表。到达顺序会反转——插入排序从 队尾跳到前列——没有任何公式比亲眼看到更能讲清这一点。
三个常见错误
“快速排序永远最快。”平均而言它属于最快的一类,但简单的快速排序最坏情况是 O(n²),例如基准总是落在列表的一端时。归并排序和堆排序无论输入如何都保持 O(n log n)。
“简单的平方级算法毫无用处。”插入排序广泛用于小列表,在几乎有序的列表上表现很好。实际使用的排序程序通常是混合算法,处理小段数据时会改用插入排序。
“稳定排序就是永不出错的排序。”稳定性有确切的含义:键相同的元素在排序后保持原来的先后顺序。归并排序和插入排序是稳定的;快速排序和堆排序的常见写法则不是。
访客常问
在实际代码中应该用哪种排序算法?
几乎总是用语言内置的排序:Python 的 sorted()、JavaScript 的 Array.sort() 或 Java 用于对象的 Arrays.sort()。它们都是工程化的混合算法(Python 和 Java 使用 Timsort),时间为 O(n log n),稳定,并经过数百万用户检验。本页面的六种算法讲的是这些工具背后的思想,而不是要取代它们。
冒泡排序这么慢,为什么还要教?
因为它是最简单的排序思想:比较相邻元素,逆序就交换,重复。看着它在竞速模式中被归并排序甩开,比任何公式都更能讲清 O(n²) 增长。提前退出也说明:同一算法在已经有序的输入下可以是 O(n),一般情况下是 O(n²)。
排序稳定是什么意思?
稳定排序保持相等元素原来的相对顺序。当按多个关键字排序时这很重要:先按姓名、再按成绩用稳定算法给班级排序,成绩相同的学生仍保持字母顺序。归并、插入和冒泡排序是稳定的;通常实现的选择、快速和堆排序不是。
快速排序平均是 O(n log n),为什么不总是更快?
因为它最坏情况是 O(n²):运气不好选到坏主元,每次划分只剥离一个元素。好的实现用三数取中选主元(如本模拟器)或随机化来避免。归并排序保证 O(n log n),但需要 O(n) 额外内存;堆排序保证 O(n log n) 且原地进行,但内存跳跃访问不受现代缓存欢迎。
模拟器真的在运行算法吗,还是只是动画?
真的在运行。每个算法都执行真实逻辑并发出步骤事件——比较、交换、覆写、主元、归并、堆化——由动画图表回放。竞速模式下六种算法用同一输入并排运行,所以比较是公平的。单词模式排序文本时不区分声调和大小写。
大 O 记号到底在数什么?
基本步骤数随输入如何增长,忽略常数因子。O(n²) 表示输入翻倍,工作量约变为四倍;O(n log n) 表示输入翻倍,工作量只多一点。当 n = 1,000,000 时,就是约一万亿次操作与两千万次操作的区别——几分钟甚至几小时对一眨眼。
资料与延伸阅读
- Introduction to Algorithms — MIT Press (Cormen et al.)
- Sorting algorithm — Wikipedia
- Dictionary of Algorithms and Data Structures — NIST
- Algorithms course — Khan Academy
引用本展品
Eurekarium. (2026). 排序实验室. https://eurekarium.com/zh-hans/computing/sorting-lab/
最近更新: