各种排序算法总结
开篇介绍
大家好，我是Java最全面试题库的提裤姐，今天这篇是数据结构与算法的第六篇，主要是对排序算法的总结；在后续，会沿着第一篇开篇的知识线路一直总结下去，做到日更！如果我能做到百日百更，希望你也可以跟着百日百刷，一百天养成一个好习惯。
前面几篇文章已经把排序的各种方法都介绍了一遍 今天就来总结对比一下这些排序方法：
| 排序方法 | 最好时间 | 平均时间 | 最坏时间 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
| 直接选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 冒泡排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(n1.25) | O(1) | 不稳定 | ||
| 快速排序 | O(nlgn) | O(nlgn) | O(n2) | O(lgn) | 不稳定 |
| 堆排序 | O(nlgn) | O(nlgn) | O(nlgn) | O(1) | 不稳定 |
| 归并排序 | O(nlgn) | O(nlgn) | O(nlgn) | O(n) | 稳定 |
| 基数排序 | O(d·n+d·rd) | O(d·n+d·rd) | O(d·n+d·rd) | O(n+rd) | 稳定 |
通常可按平均时间将排序分为四类：
(1)平方阶(O(n2))排序，一般称为简单排序：例如直接插入、直接选择和冒泡排序；
(2)线性对数阶(O(nlgn))排序：如快速、堆和归并排序；
(3)O(n1+ε)阶排序，ε是介于0和1之间的常数，即0<ε<1，如希尔排序；
(4)线性阶(O(n))排序：如桶、箱和基数排序。
在比较同数量级的各种排序方法的优劣时，常数因子必须考虑。
在表中给出了几种排序的实际运行时间，其中前5行使用随机数据，后2行分别使用递增和递减有序的数据。被排序的数据是整数数组，各种排序方法使用相同的输入实例。
| n | 直接插入排序 | 直接选择排序 | 冒泡排序 | 堆排序 | 快速排序 |
|---|---|---|---|---|---|
| 4000 | 5.67 | 17.30 | 15.78 | 0.13 | 0.07 |
| 8000 | 23.15 | 29.43 | 64.03 | 0.28 | 0.17 |
| 10000 | 35.43 | 46.02 | 99.10 | 0.35 | 0.22 |
| 15000 | 80.23 | 103.00 | 223.28 | 0.58 | 0.33 |
| 20000 | 143.67 | 185.05 | 399.47 | 0.77 | 0.47 |
| 20000（升序） | 0.05 | 185.78 | 0.03 | 0.75 | 0.23 |
| 20000（降序） | 286.92 | 199.00 | 584.67 | 0.80 | 0.28 |
从表可看出，简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：
①待排序的记录数目n；
②记录的大小(规模)；
③关键字的结构及其初始状态；
④对稳定性的要求；
⑤语言工具的条件
⑥存储结构；
⑦时间和辅助空间复杂度等。
依据以上因素，可得出如下结论：
(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好，这一点可从表看出；否则因为直接选择移动的记录数少于直接插入，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜。
(3)若n较大，则应采用时间复杂度为 O(nlgn)的排序方法：快速排序、堆排序或归并排序。
