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

基本概念

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

整个算法分为若干轮次进行。在当前轮次中，对于选定的数组范围[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 (n l o g n)$ ；
最坏情况：每次划分得到的子序列只比上一层长度少1， $O(n^2)$ ；
平均情况： $O(n log_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;
    }
};