常见排序算法时间复杂度和稳定性怎么对比记
回答
比较类排序里,快速、归并、堆排序平均都是 O(n log n),冒泡、插入、选择是 O(n^2)。稳定的有冒泡、插入、归并(值相等的元素相对次序不变),不稳定的有快速、堆、选择、希尔。快速排序基准选得差(如序列已有序且总取首元素)时退化为 O(n^2);归并需要 O(n) 额外空间;堆排序原地但不稳定。
- 冒泡:平均 O(n^2);已有序且带提前结束标志时 O(n);空间 O(1);稳定
- 插入:平均 O(n^2);已有序时 O(n);空间 O(1);稳定
- 选择:O(n^2),与初始顺序无关;空间 O(1);不稳定
- 希尔:取决于增量序列,通常介于 O(n log n) 与 O(n^2) 之间;空间 O(1);不稳定
- 快速:平均 O(n log n),退化时 O(n^2);空间 O(log n)(递归栈);不稳定
- 归并:O(n log n);空间 O(n);稳定 · 堆:O(n log n);空间 O(1);不稳定
例:选择排序处理 [5a, 5b, 2](5a、5b 值相同,字母只作标记):第 1 趟把 2 与首元素 5a 交换,得 [2, 5b, 5a],两个 5 的先后次序被颠倒,说明选择排序不稳定(已用程序复现)。
依据:严蔚敏《数据结构》「内部排序」一章对各排序方法时间复杂度与稳定性的讨论。
相关官方导图:数据结构期末 · 图、查找与排序