排序算法总结

排序稳定性

定义：假定在待排序的序列中，存在多个相同值，若经过排序，这些值的相对次序保持不变，即在原序列中，r [i] = r [j]，且 r [i] 在 r [j] 之前，而在排序后的序列中，r [i] 仍在 r [j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序稳定性很容易被认为是排序速度的稳定性，比如插入排序就是速度不稳定的算法。

排序稳定性对于基础类型（如 int、double 等）没有任何意义，而对非基础类型则具有重要意义。设想下面两个场景：

1. 打印整个年级的名册，要求先按班级排序，然后班级内部再按年龄排序，这就要求排序算法具有稳定性。
2. 你在淘宝上购买商品，如果先将价格从低到高排列，再将评价从高到低排列，那么排在前面的就是物美价廉的商品。

那么哪些排序算法具有稳定性呢？注意，排序稳定性取决于具体实现的细节，例如冒泡排序、选择排序以及归并排序，它们既可以是稳定排序，也可以是不稳定排序，关键取决于你如何处理两个相等的值（把前者仍放前面，后者仍放后面） 。其他排序算法的稳定性见下表。

综合比较

• 基于比较的排序，时间复杂度极限为 O(NlogN)
• 不基于比较的排序，对数据形式有较大要求，且不适合对象排序
• 时间复杂度 O(NlogN) ，空间复杂度 O(N)，且稳定的算法是不存在的
• 随机快排之所以快于归并和堆排序，是因为其常数时间是最小的
• 追求速度 —— 随即快排，追求空间 —— 堆排序，追求稳定性 —— 归并排序

工程改进

排序算法在工程上的改进可以大致从以下两个角度：

1. 稳定性

   比如在 java 中的 arrays.sort () 中，当元素是对象时，它会使用归并排序以追求稳定性；当元素是基础类型时，它会使用快速排序以追求速度。

2. 综合利用

   比如 C 语言中的 std::sort 函数，针对大数据量，使用快排；若快排递归深度超过阈值，改用堆排序，防止快排递归过深，同时保持时间复杂度仍是 O (NlogN)；当数据规模小于阈值时，改用插入排序，因为插入排序的常数时间小于快排，因此处理小规模数据时更有优势。