3-1 排序

1.排序算法基础：从哪几个角度衡量排序算法

前面我们已经介绍过，衡量一个算法的优劣从时间复杂度、空间复杂度两个角度去分析。
那么排序算法呢？分析上面两个方面是否足够?让我们带着这个问题去阅读下面内容。

1.1 时间复杂度

对于排序算法的时间复杂度，我们需要从最好、最坏、平均时间复杂度去分析。对于排序算法来说，待排序数据的有序度很大程度上会影响算法的执行时间，接近有序的数据和完全无序的数据需要的时间是完全不一样的。

之前我们使用大O表示法来描述时间复杂度，通常会省略低阶、常数、系数，但是在排序算法中，我们要排序的数据可能达不到那么大，只有几十或几百，这个时候我们就需要综合低阶、常数项各方面因素来衡量。

1.2 空间复杂度

前面我们讲过，算法在执行过程中的内存消耗可以用空间复杂度来衡量，排序算法当然也是如此。除了空间复杂度外，我们还可以根据排序算法是否需要非常量级的内存完成排序操作，将排序算法分为：原地排序算法（在原有内存空间即可完成排序），非原地排序算法（除原有内存空间外，还需非常量级的内存空间才能完成排序）。

根据上述，我们可以得出结论：原地排序算法的空间复杂度一定是 ，但空间复杂度是 的排序算法不一定是原地排序算法。

1.3 算法稳定性

排序算法的稳定性是指：在排序过程中，若遇到相同的元素是否交换，若无需交换，则称为稳定排序算法，反之称为不稳定排序算法。
我们为什么要区分算法是否是稳定算法呢？下面举一个例子：
假设我们有一批订单，需要按照下单时间进行排序，下单时间相同的按照金额进行排序。
平常我们的思路可能是：先将订单按照下单时间排序，然后筛选出下单时间相同的订单段，然后对一个个订单段按照金额进行排序。思路非常简单，但是实现起来非常复杂！

如果我们换个思路呢？先将订单按照金额进行排序，然后使用稳定排序算法按照下单时间对订单进行排序，这样我们就得出了最终结果，而且代码实现起来相当简单。

1.4 小结

对于排序算法来说，我们在分析时间、空间复杂度时会更细致一些，因为数据不同时，同一算法运行的效率都会有很大的影响。同时我们还了解了算法的稳定性，合理利用排序算法的这一特点，能够让我们思路清晰、代码简洁。

2. 排序算法

排序算法有很多种，如冒泡排序、插入排序、快速排序等等，我们根据时间复杂度将其划分为三类：