排序算法动画

模式
初始数组

未处理正在比较交换 / 写入基准(快排)读取(计数 / 基数)已就位

算法速查

算法平均最坏额外空间稳定要点
冒泡O(n²)O(n²)O(1)是相邻比较、大的往后冒;一轮没交换就提前结束,所以对几乎有序的数组很快
选择O(n²)O(n²)O(1)否每轮找最小值放到前面;比较次数固定,交换最多 n−1 次
插入O(n²)O(n²)O(1)是像理扑克牌;几乎有序时接近 O(n),小数组常用它收尾
希尔≈O(n^1.3)O(n²)O(1)否按间隔分组做插入排序(这里用 Ciura 间隔 701, 301, 132, 57, 23, 10, 4, 1)
归并O(n log n)O(n log n)O(n)是递归二分再合并;动画里的「写入」是从辅助数组写回
快速O(n log n)O(n²)O(log n)否Lomuto 分区,取中间元素做基准;重复值多时会变慢
堆O(n log n)O(n log n)O(1)否先建大顶堆,再反复把堆顶换到末尾
计数O(n + k)O(n + k)O(k)是*不做比较,统计每个值出现次数后直接写回;k 是值域大小(*这里写回的是值本身)
基数O(d·n)O(d·n)O(n)是LSD 十进制,从个位到最高位每轮按一位分桶;d 是位数

竞速模式里每个算法每秒执行相同的「步数」(一次比较、交换、写入或读取算一步),所以谁先完成就是谁的总步数最少。