共计 1257 个字符，预计需要花费 4 分钟才能阅读完成。
开篇介绍
大家好，我是 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)的排序办法：疾速排序 、 堆排序 或归并排序。
