如何分析一个排序算法
执行效率
- 最好情况、最坏情况、平均情况时间复杂度。
- 时间复杂度的系数、常数、低阶也要考虑进来。
- 比较次数和交换（或移动）次数。
内存消耗
算法的内存消耗随数据规模n的增长关系可以用空间复杂度来衡量。针对排序算法，还需引入一个新的概念：原地排序算法，特指空间复杂度为O(1)的排序算法。
稳定性
如果待排序的序列中存在值相等的元素，经过某一排序算法排序之后，相等元素之间的原有的前后顺序不变，这种算法就是稳定排序算法。通常在讲排序算法的时候都是使用整数来举例的，但是在实际的开发中，需要排序的往往是一组对象，我们需要按照对象的某一个属性key来排序，这个时候你所使用的排序算法是否具有稳定性就能体现出来了。
例如，现在要求我们对一组订单按订单金额从大到小排序，订单金额相同的按下单时间从早到晚排序。最先想到的方法可能是：我们先按照金额进行排序，然后再遍历排序过的订单数据，对每个订单金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会比较复杂。
借助稳定排序算法，我们可以先按照下单时间从早到晚排序，然后对排序完成的订单数据再使用稳定排序算法按订单金额重新排序。注意，第二次排序时要使用稳定排序算法，那么两次排序之后的结果就是题目要求的结果了。
常见的排序算法
下面的篇幅会从时间复杂度、空间复杂度、稳定性三个方面对常见的排序算法进行分析，至于相关排序算法的代码实现请点击这里查看。
1.冒泡排序
时间复杂度
- 最差时间复杂度O($n^2$)。
- 平均时间复杂度O($n^2$)。
- 要排序的数据已经是有序的了，最好时间复杂度O(n)。
空间复杂度
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。
稳定性分析
当相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
2.插入排序
时间复杂度
- 最差时间复杂度O($n^2$)。
- 平均时间复杂度O($n^2$)。
- 如果要排序的数据已经是有序的了，每次只需要比较一个数据就能确定插入的位置，最好时间复杂度O(n)。
空间复杂度
排序过程只涉及到比较和交换操作，空间复杂度为O(1)，是一个原地排序算法。
稳定性分析
对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，保证相等元素原有的前后顺序不变，所以插入排序是稳定的排序算法。
3.希尔排序
时间复杂度
实质上就是通过步长进行分组插入排序，递减步长直至为1，所以时间复杂度取决于步长序列的选取。
- 最差时间复杂度O($nlog^{2n}$)。
- 平均时间复杂度O($nlog^{2n}$)。
- 要排序的数据已经是有序的了，最好时间复杂度O(n)。
空间复杂度
排序的思想还是插入排序，只是进行了分组处理，所以排序过程只涉及到比较和交换操作，空间复杂度为O(1)，是一个原地排序算法。
稳定性分析
对于值相同的元素，分组插入排序时可能存在于不同的组中，组内元素会发生交换操作，所以希尔排序不稳定。
4.选择排序
时间复杂度
- 最差时间复杂度O($n^2$)。
- 平均时间复杂度O($n^2$)。
- 最好时间复杂度O($n^2$)。
空间复杂度
排序过程只涉及到比较和交换操作，空间复杂度为O(1)，是一个原地排序算法。
稳定性分析
选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样就破坏了稳定性。
5.堆排序
时间复杂度
第一步建堆的时间复杂度为O(n)，第二步遍历堆内元素进行堆化的时间复杂度为O($nlog^n$)，所以总的时间复杂度为O($nlog^n$)。
空间复杂度
建堆和堆化操作只需要极个别临时存储空间，所以空间复杂度为O(1)。
稳定性分析
堆排序不是稳定的排序算法，因为在堆化的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序
6.归并排序
时间复杂度
- 最差时间复杂度O($nlog^n$)。
- 平均时间复杂度O($nlog^n$)。
- 最好时间复杂度O($nlog^n$)。
空间复杂度
由于归并排序的合并函数在合并两个有序数组为一个有序数组时，需要借助额外的存储空间，临时的额外存储空间最大也不会超过n个数据的大小，所以空间复杂度就是O(n)。
稳定性分析
归并算法是否稳定得看merge函数的具体实现，也就是两个有序数组合并成一个有序数组的代码。在合并过程中，两个数组元素相同时取前面数组中的那个元素作为新数组的元素即可保证排序的稳定性。所以归并排序算法是稳定的排序算法。
7.快速排序
时间复杂度
- 最差时间复杂度O($n^2$)。
- 平均时间复杂度O($nlog^n$)。
- 最好时间复杂度O($nlog^n$)。
空间复杂度
分区操作可通过类似插入排序元素交换的方式将时间复杂度控制在O(1)，双指针的使用，所以快速排序是一个原地排序算法。
稳定性分析
因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列[6,8,7,6,3,5,9,4]在经过第一次分区操作之后，两个6的相对前后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。
8.桶排序
时间复杂度
如果要排序的数据有n个，我们把它们均匀地划分到m个桶内，每个桶就有k=n/m个元素。每个桶内部使用快速排序，时间复杂度为O($k*log^k$)。m个桶排序的时间复杂度就是O($m*k*log^k$)。因为k=n/m，所以整个桶排序的时间复杂度就是O($n*log^{n/m}$)，当桶的个数m接近数据个数n时，$log^{n/m}$就是一个非常小的常量，忽略常量系数，那么桶排序的时间复杂度就接近O(n)。
空间复杂度
很明显，桶排序需要声明m个桶来存放待排序的n个元素，所以空间复杂度为O(m + n)。
稳定性分析
桶排序的稳定性取决于桶内元素排序所使用的排序算法，通常认为是稳定的。
9.计数排序
时间复杂度
计数排序可以认为是一种特殊的桶排序，也属于线性排序算法。时间复杂度为O(n + k)，k为数据范围。
空间复杂度
需要创建统计数组，数组大小取决于数据范围k。
稳定性分析
排序过程中未进行过元素的交换操作，属于稳定排序算法。
10.基数排序
基数排序对待排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之前要有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法（桶排序或计数排序）来排序。
时间复杂度
位排序依赖于线性排序算法，所以自身也属于线性排序算法，最好时间复杂度情况能达到O(n)。
空间复杂度
位排序依赖于线性排序算法，非原地排序算法。
稳定性分析
取决于位排序时所使用的排序算法的稳定性，通常认为是稳定的。
思考
冒泡排序和插入排序的时间复杂度都是O($n^2$)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？
对比一下冒泡排序和插入排序的代码实现你就会发现，冒泡排序的元素交换需要借助一个临时变量temp，需要三次赋值操作。而插入排序的数据移动只需一次赋值操作即可完成。
快速排序的最坏情况时间复杂度为O($n^2$)，相比于最好、平均、最坏情况时间复杂度都是O($n*log^n$)的归并排序为啥更受欢迎呢？
归并排序空间复杂度为O(n)，非原地排序算法。所以，夸张点讲，如果要排序100MB的数据，除了数据本身占用的内存之外，排序算法还要额外再占用100MB的内存空间，内存耗费就翻倍了。
优化快速排序，如何选择合适的分区点？
- 三数取中法，从区间的首、尾、中分别取出一个数，然后对比大小，取3个数的中间值作为分区点。
- 随机法，从区间中随机选取一个数作为分区点。
如何设计一个通用的、高效的排序函数
回顾一下前面讲到的几种排序算法：
| 算法 | 时间复杂度 | 是原地排序？ | 是稳定排序？ |
|---|---|---|---|
| 冒泡排序 | O($n^2$) | 是 | 是 |
| 插入排序 | O($n^2$) | 是 | 是 |
| 选择排序 | O($n^2$) | 是 | 是 |
| 希尔排序 | O($n^2$) | 是 | 否 |
| 归并排序 | O($nlog^n$) | 否 | 是 |
| 快速排序 | O($nlog^n$) | 是 | 否 |
| 堆排序 | O($nlog^n$) | 是 | 否 |
| 桶排序 | O(n) | 否 | 是 |
| 计数排序 | O(n+k)k是数据范围 | 否 | 是 |
| 基数排序 | O(dn)d是纬度 | 否 | 是 |
线性排序算法的时间复杂度比较低，适用场景比较特殊。所以如果要写一个通用的排序函数，不能选择线性排序算法。对于小规模数据进行排序，可以选择时间复杂度是O($n^2$)的算法，如果对大规模数据进行排序，时间复杂度是O($nlog^n$)的算法更加高效。所以根据不同的数据规模选择合适的排序算法就显得很关键。
例如C语言的qsort()函数的会优先使用归并排序来排序输入数据，因为归并排序的空间复杂度是O(n)，所以对于小数据量的排序，比如1KB、2KB等，归并排序额外需要1KB、2KB的内存空间，相对于计算机内存来说，这点内存消耗不算啥问题，更多的是对速度的追求，以空间换时间。但如果数据量太大，qsort()会改用快速排序算法来排序，并采用“三数取中发”选择分区点。在快速排序的过程中，当排序的的区间元素个数小于等于4时，qsort()就退化为插入排序，不再用递归来做快速排序。