排序算法是数据结构里面非常重要的一部分,每个排序方法都有各自的特点及适用条件,以下对各自的时间复杂度和方法概要做了总结,并对一些要点做出自己的思考。
1. 首先比较一下7种算法的各项指标:
排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | 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^1.3) | O(n^2) | O(1) | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
2. 排序算法的分类及内容
插入排序类
直接插入排序
- 类比于理牌,将一个记录插入到已经排好序的有序表中,得到新的、记录数加1的有序表。
希尔排序
- 将相距某个增量的记录组成一个子序列,在子序列中进行排序后得到基本有序的结果。
选择排序类
简单选择排序
- 通过n-i次关键字的比较,从n-i+1个记录中选出关键字最小的记录,并与第i个记录交换。
堆排序
- 先将序列构造成大顶堆,再将顶部的值一个个地移走,同时还要保证大顶堆的状态。
交换排序类
冒泡排序
- 两两比较相邻记录的关键字,如果反序就交换,直到没有反序。
快速排序
- 每一趟排序将待排记录分割成两部分,一部分的关键字均比另一部分小,再重复操作。
归并排序类
归并排序
- 将初始序列堪称n个有序的子序列,然后重复两两归并的操作,最终得到有序序列。
3. 一些注意点
(1)冒泡排序的优化:未优化的算法会对有序序列做重复同样的没有必要的比较工作,可以通过增加标记变量flag改进代码。
(2)希尔排序的关键是其增量序列,大量研究表明,增量序列为dlta[k]=2^(t-k+1)-1(0<=k<=t<[log2(n+1)])时,可将时间复杂度提高为O(n^(3/2))。注意:增量序列的最后一个增量必须等于1。
(3)堆排序时,通过不停取最大堆的根节点进行排序,应该也可通过取最小堆的叶子节点进行排序,是另一种思路。
(4)归并排序可通过递归或非递归实现,都有相应的巧妙点,递归实现时临时存储变量的定义位置,在递归开始前规定整个临时变量的空间,可以减少空间定义的操作时间、非递归实现时while循环内有要进行两次归并,使最终排序结果永远保存在原始数组中、非递归的迭代方法,避免了递归深度为log2n的栈空间,空间只是用到申请归并临时用的数组,因此空间复杂度为O(n)。
归并排序的程序:(以java为例)
\1. 分
1 | public static void mergeSort(int[] array, int left, int right){ |
\2. 并
1 | public static void merge(int[] arr, int left, int mid, int right){ |
(5)快速排序的优化:1).优化选取枢轴:如三数取中;2).优化不必要的交换:采用替换而不是交换进行中间过程的操作;3).优化小数组时的排序方案:添加阈值,对于小数组用直接插入算法进行操作,利用两种排序的优势完成排序工作;4).优化递归操作:因为快速排序在其尾部有两次递归操作,对函数实施尾递归优化。采用迭代而不是递归的方法可以缩减堆栈的深度,提高整体性能。
本文链接: http://example.com/2021/06/28/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E2%80%94%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84%E6%80%BB%E7%BB%93%E5%92%8C%E6%80%9D%E8%80%83/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!