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. 发散性思维
上面我们对比切了解到了各种排序的应用情况及优缺点，任何一种排序都不是十全十美的，因此我们最好的方式就是扬长避短，那么请你设计一个算法，能够主动的通过一次遍历去发现数据的情况，究竟最适合何种排序为妙呢？
更多训练见：排序算法专题训练
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程