【算法】在？复习一下快速排序？

基本概念

快速排序是一种基于交换的排序算法，该算法利用了分治的思想。

整个算法分为若干轮次进行。在当前轮次中，对于选定的数组范围[left, right]，首先选取一个标志元素pivot，将所有小于pivot的元素移至其左侧，大于pivot的则移动至其右侧，记录下最终pivot所处的位置pivot_pos。然后再利用递归，分别对左侧区间[left, pivot_pos - 1]和右侧区间[pivot_pos + 1, left]执行相同操作，依次类推，最终对整个数组完成排序。

以数组[16, 1, 2, 25, 9, 2, 5]为例，在递归实现中，其排序过程中交换策略如下图所示。当pivot_pos与i相等时，不需要交换，之所以先将pivot_pos++再交换的原因是，此时i指向的是小于pivot的元素，而pivot_pos是小于标志元素范围的右边界（如图），如果pivot_pos + 1 = i，则直接将这个右边界扩大1即可，而无需交换。如果不是，则将pivot_pos += 1以指向这个大于pivot的元素，并将其与小于pivot的array[i]进行交换，从而扩大右边界。下面给出了递归实现的示例代码。

int partition(int *array, int left, int right) {
    // * 默认选定首个元素为划分元素
    int pivot_pos = left, pivot_val = array[left];
    // * 遍历，将小于划分元素的值交换至其左侧
    for (int i = left + 1; i <= right; ++i) {
        if (array[i] < pivot_val) {
            pivot_pos += 1;
            if (pivot_pos != i) {
                swap(array[i], array[pivot_pos]);
            }
        }
    }
    array[left] = array[pivot_pos];
    array[pivot_pos] = pivot_val;
    return pivot_pos;
}

// * 递归版快速排序 O(nlogn)
void quickSort(int *array, int left, int right) {
    if (left < right) {
        int pivotpos = partition(array, left, right);
        quickSort(array, left, pivotpos - 1);
        quickSort(array, pivotpos + 1, right);
    }
}

算法分析

时间复杂度：

• 最好情况：每次划分均得到等长的两个子序列，$O(nlogn)$；
• 最坏情况：每次划分得到的子序列只比上一层长度少1，$O(n^2)$；
• 平均情况：$O(nlo{g}_n)$

此外，快速排序是一种不稳定的排序算法。

技巧应用

面试题 17.14. 最小K个数 - 力扣（LeetCode）

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
提示：
0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))

请注意，上面这个题不要求返回的顺序。我们可以用快速排序对该数组进行排序操作。考虑一下快速排序的流程，是先对整体数组进行划分，然后再依次对划分元素的左侧和右侧进行划分，逐层递归。当划分元素的位置等于k或k + 1时，[0, k - 1]实际上已经是数组前k小的数了，没有必要继续对数组做完全排序，因此可以将pivotpos == k || pivotpos == k + 1作为递归出口。

示例代码如下：

class Solution {
// 采用STL迭代器组合表示待排序的范围range
private:
    using Iter = vector<int>::iterator;
    Iter partition(Iter left, Iter right) {
        Iter pivot_pos = left;
        int pivot_val = *left;
        for (Iter i = left + 1; i < right; ++i) {
            if (*i < pivot_val) {
                pivot_pos += 1;
                if (pivot_pos != i) {
                    iter_swap(pivot_pos, i);
                }
            }
        }
        iter_swap(left, pivot_pos);
        return pivot_pos;
    }

    void quicksort(Iter left, Iter right, Iter tar) {
        if (left < right) {
            Iter pivot_pos = partition(left, right);
            if (pivot_pos > tar + 1) {
                quicksort(left, pivot_pos, tar);
            }
            if (pivot_pos < tar) {
                quicksort(pivot_pos + 1, right, tar);
            }
            // 仅当等于tar或者tar+1时，
            // 才可判定pivot_pos的左侧范围为前k小或前k+1小
        }
    }

public:
    vector<int> smallestK(vector<int>& arr, int k) {
	    if (arr.empty() || k == 0) return {};
        quicksort(arr.begin(), arr.end(), arr.begin() + k - 1);
        vector<int> rtn(arr.begin(), arr.begin() + k);
        return rtn;
    }
};

拓展

在快速排序算法中，一个关键操作就是选择基准点（Pivot）：元素将被此基准点分开成两部分。

最经常使用的就是选择一个区间的首元素或者尾元素，如本文所给出的示例。但是当数组部分有序时，这样做通常会使算法陷入坏情况，从 $O(nlo{g}_n)$ 劣化到 $O(n^2)$。

研究人员为此设计了一个快速排序的变体，选择首、尾、中间元素之中的中位数作为基准，依次避免特殊情况下算法劣化到 $O(n^2)$。但是即便性能有所提升，但是仍然有机会针对这种算法设计出一些特殊构造数组，以延长排序时间。这可能会造成服务器计算时间过程，进而为拒绝服务攻击提供可乘之机。

大卫·穆塞尔在1997年提出了内省排序算法introsort。旨在改善上述情况。introsort的主要步骤如下：

1. 快速排序：最初使用快速排序对数组进行排序。
2. 递归深度检查：在递归过程中，检查当前的递归深度。如果深度超过 $2logn$，则切换到堆排序。
3. 堆排序：当递归深度过深时，使用堆排序对当前子数组进行排序。
4. 插入排序：在数组小于一定阈值（通常是16或更小）时，使用插入排序进行排序，以提高小数组排序的效率。

使用这种组合算法，可以在正常快速排序算法的平均和最坏情况下，将时间复杂度均保持为$nlogn$。

C++ STL算法库中的sort函数，在早期版本（LWG713之前）未对最坏情况的时间复杂度做要求，那个时候的标准库使用普通qsort实现就符合要求。在此之后，标准对最坏情况的时间复杂度进行了修正，后面的标准库实现版本使用的就是introsort算法。

LWG-xxx : 由 ISO C++ 标准委员会的图书馆工作组（LWG）跟踪的某个特定问题编号。