排序算法总结-数据结构与算法教程
1. 排序汇总
|
类别 |
排序方法 |
时间复杂度 |
空间复杂度 |
稳定性 |
||
|
平均情况 |
最好情况 |
最坏情况 |
||||
|
插入排序 |
直接插入 |
O(n^2) |
O(n) |
O(n^2) |
O(1) |
稳定 |
|
希尔排序 |
O(n^2) |
O(n) |
O(n^2) |
O(1) |
不稳定 |
|
|
选择排序 |
直接选择 |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
不稳定 |
|
堆排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
不稳定 |
|
|
交换排序 |
冒泡排序 |
O(n^2) |
O(n) |
O(n^2) |
O(1) |
稳定 |
|
快速排序 |
O(nlogn) |
O(nlogn) |
O(n^2) |
O(nlogn) |
不稳定 |
|
|
归并排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
稳定 |
|
2.各个排序面对数据的适用情况与小技巧
选取几个比较有特点有代表性质的排序算法
快速排序算法的效率体现在序列越乱的时候，效率越高，当数据趋于一个有序状态时（无论是顺序还是逆序），将会退化为冒泡排序，当数据完全处于逆序状态时，快速排序将会消耗极大的时间，因此有些OJ的快速排序模板测试题并不能直接写快排通过【毒瘤数据，超大完全逆序数据】，可以尝试适用rand()产生随机数的方法将整体数据打乱再使用快速排序，可以极大的减少运行时间。
直接插入排序有着稳定和速度快的优点，缺点是比较次数越少，插入点后的数据移动就越多，特别是数据庞大的时候就需要大量的移动数据。
堆排序作为一个相对比较复杂的排序，我们可以更加深入的去借鉴思想，比如有问题要求在n个数据中选出或者排序出前k个数据，利用堆排序的思维可以不将全部的n进行排序而只操作出前k个数据的情况，这个思维是很重要的。
希尔排序最主要的操作是比较而不是交换，因此在小数组的情况下是比快速排序和堆排序要快的，但是涉及大量数据时依旧不如快排。
对于绝大多数排序在数据达到顺序的情况下并没有办法直接结束，在前置处理数据不是很大的情况下，可以设置一个flag标记，当数据完全处于顺序的情况下直接强制退出排序，以达到减少运行时间的效果，当然前置处理数据在总执行步骤中占比不易过大，如总执行100次，在执行95次的时候已经达到顺序，有5次循环浪费，这样的情况浪费时间不如你而外增添的标记判断时间，就不需要这个flag标记。
3. 发散性思维
上面我们对比切了解到了各种排序的应用情况及优缺点，任何一种排序都不是十全十美的，因此我们最好的方式就是扬长避短，那么请你设计一个算法，能够主动的通过一次遍历去发现数据的情况，究竟最适合何种排序为妙呢？
作者：喵哥笔记
