对排序算法的总结和提升

通过前面章节的学习，读者已经掌握了常用的几种排序算法，包括冒泡排序、插入排序、选择排序、希尔排序、归并排序、快速排序等，接下来带大家快速梳理一下。

时间复杂度

下表罗列了不同排序算法的时间复杂度。

对于给定的待排序序列，经常会包含相同的元素，例如：

3 1 2 4 2

序列中包含两个元素 2，为了区分它们，我们分别称它们为 "红 2" 和 "绿 2"，它们的相对位置是：红 2 位于绿 2 的左侧，或者说绿 2 位于红 2 的右侧。

如果使用某种排序算法对序列进行排序，得到的有序序列是：

升序序列：
1 2 2 3 4
降序序列：
4 3 2 2 1

红 2 依然位于绿 2 的左侧，它们的相对位置保持不变，表明当前使用的排序算法是稳定的；反之，如果红 2 和绿 2 的相对位置发生了改变，那么这个排序算法就是不稳定的。

下表罗列了不同排序算法的稳定性。

注意，表格中标记“稳定”的排序算法，比如计数排序、基数排序、桶排序等，受实现思路的影响，也可能变得不稳定。

以桶排序算法为例，如果各个桶内存储相同元素时改变了它们的相对位置，又或者桶内排序时采用了不稳定的排序算法，那么整个算法就不是稳定的。

所谓原地排序，指的是算法在排序过程中，主要使用待排序序列占用的内存空间，最多额外创建几个辅助变量，而不再申请过多的内存空间。

更直白一点讲，直接修改待排序序列本身，把原有的待排序序列变得有序，这样的排序算法就是原地排序的。

原地排序算法的空间复杂度为 O(1)。

下表给大家罗列了哪些排序算法是原地排序的。