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

1. 线性排序算法的时间复杂度比较低，适用场景比较特殊，所以不能选择线性排序算法。
2. 为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。
3. 归并排序并不是原地排序算法，空间复杂度是 O(n)。
4. 所以快速排序比较适合来实现排序函数。

但是，快速排序在最坏情况下的时间复杂度是 O(n²)，如何来解决这个“复杂度恶化”的问题呢？

如何优化快速排序？

为什么最坏情况下快速排序的时间复杂度是 O(n²) 呢？
如果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，时间复杂度就会退化为 O(n²)。** O(n²) 时间复杂度出现的主要原因还是因为我们分区点选的不够合理。**

如何来选择分区点呢？

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

1. 三数取中法

我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。但是，如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。

2. 随机法

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

防止快速排序递归的堆栈溢出：

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

在小规模数据面前，O(n²) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长。
解释：在大 O 复杂度表示法中，我们会省略低阶、系数和常数，也就是说，O(nlogn) 在没有省略低阶、系数、常数之前可能是 O(knlogn + c)，而且 k 和 c 有可能还是一个比较大的数。