查找与排序除了需要掌握代码外，还需要掌握各种性能对比，本文对常见的排序算法的性能进行对比。
如有错误，请读者指正。
| 排序算法 | 时间复杂度 |
空间复 杂度 |
稳定性 | 适用性 |
一趟是否能 确定一个位置 |
比较次数是否 与初态无关 |
|---|---|---|---|---|---|---|
| 直接插入排序 | 最好：O(n) | O(1) | 稳定 |
顺序表 链表 |
否 | 否 |
| 最坏：O(n^2) | ||||||
|
平均： O(n^2) |
||||||
| 折半插入排序 | 最好：O(nlogn) | O(1) | 稳定 | 顺序表 | 否 | 否 |
| 平均：O(n^2) | ||||||
|
平均： O(n^2) |
||||||
| 希尔排序 | 不确定 | O(1) |
不稳定 |
顺序表 | 否 | 否 |
| 冒泡排序 | 最好：O(n) | O(1) | 稳定 |
顺序表 链表 |
是 |
否 |
| 最坏：O(n^2) | ||||||
|
平均： O(n^2) |
||||||
| 快速排序 | 最好：O(nlogn) | O(nlogn)~O(n) |
不稳定 |
顺序表 |
是 |
否 |
| 最坏：O(n^2) | ||||||
|
平均： O(nlogn) |
||||||
| 简单选择排序 |
O(n^2) |
O(1) |
不稳定 |
顺序表 链表 |
是 |
是 |
| 堆排序 |
O(nlogn) |
O(1) |
不稳定 |
顺序表 |
是 |
否 |
| 归并排序 |
O(nlogn) |
O(n) | 稳定 | 顺序表 | 否 | 否 |
| 基数排序 |
O(d(n+r)) |
O(r) | 是 | 顺序表 | 否 |
是 |
稳定性解释：
希尔排序：举例，序列
3
5
10
8
7
2
8
1
20
6
，d=2。分成两组（3 10 7
8
20） 和（5
8
2 1 6）
第一组的8在第二组的后面，则最后排序为（3 7
8
10 20 1 2 5 6
8
）。可见，位置会变化，不稳定。
快速排序：举例，序列
49
38
49
20 97 76 ，枢轴20，从左找寻第一个比20大的，即无下划线49，交换后两个49位置变化。
则最后排序为 20 38
49
49
76 97 可见，位置会变化，不稳定。
简单选择排序：举例，序列
5
4 3
5
2 1，根据算法，第一趟排序，假设第一个5为最小值，最后与1交换，
则最后排序为 1 2 3 4
5
5
。可见，位置会变化，不稳定。
堆排序：举例，例如3
27
36
27
3
27
36
27
3输出后，将带下划线的27调整至堆顶，带下划线的27先输出，故不稳定。
更多数据结构实现：
数据结构严蔚敏版的实现（含全部代码）
有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。