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