排序算法总结
文章目录
排序总结
这几天一直在写排算法，这属于最基本的算法，以前只是知道，也没怎么用过，最近重新温故复习，总结一下。
其实排序分为内部排序和外部排序，区别在于是否将排序记录全部放置在内存中，外部排序主要用于大量数据的排序，如多路归并排序。最近几天写的都是内部排序。主要可以分为四类：
- 插入类排序：直接插入排序和希尔排序。
- 选择类排序：简单选择排序和堆排序。
- 交换排序类：冒泡排序和快速排序。
- 归并类排序：归并排序。
简单的算法：冒泡、简单选择、直接插入。
改进的算法：希尔、堆、归并、快速。
算法指标对比
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn)~O(n^2) | O(n^3/2) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
算法的选择则需要根据需要选择，比如追求稳定性来说归并排序是个好选择，但是会牺牲空间复杂度。 再比如数据量不大但是关键字信息量大（如数字很大），交换和移动次数多则会耗费和迪诺时间，此时应该选择移动次数较少的简单排序算法。
