找到合适的排序算法

如何选择合适的排序算法？

线性排序算法的时间复杂度比较低，适用场景比较特殊。所以如果要写一个通用的排序函数，不能选择线性排序算法。

如果对小规模数据进行排序，可以选择时间复杂度是 O(n^2) 的算法；如果对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。

归并排序虽然时间复杂度是 O(nlogn) ，但并不是原地排序，需要消耗掉额外的空间，所以一般用快排来实现通用排序。

如何优化快速排序？

当序列本身就是有序的，然后依然每次选择最后一个数据进行分区，此时时间复杂度就会退化为O(n^2)。所以快排的优化关键在于分区点选择的合理性。

最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。

下面介绍两个分区方法。

三数取中法

我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。但是，如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。

随机法

随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选得很差的情况，所以平均情况下，这样选的分区点是比较好的。时间复杂度退化为最糟糕的 O(n2) 的情况，出现的可能性不大。

快排如何避免栈溢出

• 第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。
• 第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。

快排一定是最优解吗？

排序算法需要根据使用场景选择，比如数据量小于4时，插入排序的效率就比快排更高，所以在小规模数据面前，O(n2) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长。

而当数据占用空间比较小时，归并排序也优于快排。

Python的sorted排序使用什么方式实现

Python的sorted使用了timsort排序。

timsort结合了归并排序和插入排序（二分插入算法）。

Timsort核心过程

TimSort 算法为了减少对升序部分的回溯和对降序部分的性能倒退，将输入按其升序和降序特点进行了分区。排序的输入的单位不是一个个单独的数字，而是一个个的块-分区。其中每一个分区叫一个run。针对这些 run 序列，每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保存到栈中。合并直到消耗掉所有的 run，这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的 run 便是排好序的结果。

• 如何数组长度小于某个值，直接用二分插入排序算法
• 找到各个run，并入栈
• 按规则合并ru

Timsort性能

在平均情况下，比较排序不会比O(n log n)更快。由于Timsort算法利用了现实中大多数数据中会有一些排好序的区，所以Timsort会比O(n log n)快些。对于随机数没有可以利用的排好序的区，Timsort时间复杂度会是log(n!)。