|
快速排序的平均时间复杂度为 T(n)=kn\log n ,其中 n 为待排序序列中记录的个数， k 为某个常数。经验证明，在所有同数量级的此类（先进的）排序算法中，快速排序的常数因子 k 最小。因此，就平均时间而言，快速排序是目前被认为最好的一种内部排序方法。 ——严蔚敏、吴伟民《数据结构（C语言版）》前言： 提到内部排序，快速排序是一定会被拿出来重点介绍的。这种排序方法因其优秀的时间复杂常数和较为简单的实现而被广泛使用。然而相对于其他时间复杂度为 O(n\log n) 的排序算法，它最大的缺点是稳定性不强。当待排序列满足某些条件（如基本有序）时，快速排序的双指针会相遇在很靠近两端的位置，此时会大大影响其性能，甚至导致其时间复杂度退化为 O(n^2) ，同时在这种情况下由于递归层数过大，空间复杂度也会增加，产生栈溢出等问题，因此今天我们就来狠狠调教一下它。 一、初始版本快速排序实现 先来看看最原始版本的快速排序实现，它采用两个指针从首尾分别出发，遇到左侧大于基准数或右侧小于基准数的情况就进行交换： template
void QuickSort(vector& dataArea, long long left, long long right)
{
if (left |