快速排序

快速排序算法

快速排序是一种基于分治思想的排序算法，其基本思想是选择一个基准元素，将数组分为两部分，一部分小于基准元素，一部分大于基准元素，然后对这两部分分别进行快速排序。

时间复杂度

O(nlog⁡n)O(n \log n)，最坏情况下为 O(n2)O(n^2)。

空间复杂度

O(1)O(1)。

快速选择算法

快速选择算法是一种基于快速排序的算法，其基本思想是选择一个基准元素，将数组分为两部分，一部分小于基准元素，一部分大于基准元素，然后对这两部分分别进行快速排序。不同的是，算法只处理左右两边中有可能包含第k大的元素的那一边，/当找到第k大的元素时，算法将立刻停止排序。

时间复杂度

O(n)O(n)。

空间复杂度

O(1)O(1)。

快速选择算法与快速排序的区别

快速选择算法与快速排序的区别在于，快速选择算法只需要找到第k大的元素，而快速排序需要对整个数组进行排序。

快速选择算法的实现

快速选择算法的实现通常使用递归的方式，每次选择一个基准元素，将数组分为两部分，一部分小于基准元素，一部分大于基准元素，然后对这两部分分别进行快速选择。

例题：215. 数组中的第K个最大元素
以下是一种简易实现方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int quickSelect(vector<int>& nums, int k) {
        int pivot = nums[nums.size() - 1];
        vector<int> smaller, equal, larger;
        for(int& num : nums) {
            if(num < pivot) {
                smaller.push_back(num);
            } else if(num == pivot) {
                equal.push_back(num);
            } else {
                larger.push_back(num);
            }
        }
        if(k <= larger.size()) {
            // 第k大的元素在larger中
            return quickSelect(larger, k);
        } else if(k <= larger.size() + equal.size()) {
            // 第k大的元素在equal中
            return pivot;
        } else {
            // 第k大的元素在smaller中
            return quickSelect(smaller, k - larger.size() - equal.size());
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, k);
    }
};

以上方法虽然需要耗费更多的空间，但是直观地揭示了快速选择算法的实现原理。接下来是一种不需要创建新数组的方法，在原地交换移动元素避免耗费额外空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    pair<int, int> partition(vector<int>& nums, int left, int right) {
        int pivotIndex = left + rand() % (right - left + 1);  // 随机选择pivot，避免最坏情况退化成 O(n^2)
        int pivot = nums[pivotIndex];
        swap(nums[pivotIndex], nums[right]);
        int lt = left;  // 小于pivot的元素的右边界
        int gt = right; // 大于pivot的元素的右边界
        int i = left;   // 当前遍历的元素
        while(i <= gt) {
            if(nums[i] < pivot) {
                // 将小于pivot的元素交换到左边，注意i++，因为交换过来的元素已经小于pivot
                swap(nums[i++], nums[lt++]);
            } else if(nums[i] > pivot) {
                // 将大于pivot的元素交换到右边，注意i不移动，因为交换过来的元素需要再次判断
                swap(nums[i], nums[gt--]);
            } else {
                i++; // 等于pivot的元素
            }
        }
        return {lt, gt};
    }
    int quickSelect(vector<int>& nums, int left, int right, int k) { 
        while(left <= right) {
            auto [lt, gt] = partition(nums, left, right);
            int greaterCount = right - gt;  // 大于pivot的元素的个数
            int equalCount = gt - lt + 1;    // 等于pivot的元素的个数
            if(k <= greaterCount) {
                // 第k大的元素在gt的右边
                left = gt + 1;
            } else if(k > greaterCount + equalCount) {
                // 第k大的元素在lt的左边
                right = lt - 1;
                k -= greaterCount + equalCount;
            } else {
                // 第k大的元素在lt和gt之间
                return nums[lt];
            }
        }
        return -1;
    }
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size() - 1, k);
    }
};