开篇介绍
大家好，我是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)的排序办法：疾速排序、堆排序或归并排序。