Tong's Blog

Welcome to my Blog

0%

刷题必会：快速排序/选择

发表于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

快速排序

快速排序的逻辑是，若要对 nums[lo..hi] 进⾏排序，我们先找⼀个分界点 p，通过交换元素使得nums[lo..p-1] 都⼩于等于 nums[p]，且 nums[p+1..hi] 都⼤于 nums[p]，然后递归地去nums[lo..p-1] 和nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。

关键就在于这个分界点索引 p 的确定

image-20220322165722861

索引p左侧的元素都⽐ nums[p] ⼩，右侧的元素都⽐ nums[p]⼤，意味着这个元素已经放到了正确的位置 。

实现代码：

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
/* 快速排序主函数 */
void qsort(vector<int>& nums) {
 	// 将 nums 数组随机打乱
 	shuffle(nums);
    
    int lo = 0, hi = nums.size() - 1;
 	quicksort(nums, lo, hi);
}

/* 快速排序核⼼逻辑 */
void quicksort(vector<int>& nums, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(nums, lo, hi);
    // 现在 nums[lo..p-1] 都⼩于 nums[p]，
 	// 且 nums[p+1..hi] 都⼤于 nums[p]
 	quicksort(nums, lo, p - 1);
 	quicksort(nums, p + 1, hi);
}

/* 分界点索引 p 的确定 */
int partition(vector<int>& nums, int lo, int hi) {
    int i = lo + 1, j = hi;
    	// 将 nums[lo] 作为默认分界点 p
        while (true) {
            while (i < hi && nums[i] <= nums[lo]) {
                ++i;
            }
            while (lo < j && nums[j] >= nums[lo]) {
                --j;
            }
            if (i >= j) break;
            //此时， nums[i] > p && nums[j] < p，需交换 nums[i] 和 nums[j]
            //保证 nums[lo..i] < p < nums[j..hi]
            swap(nums[i], nums[j]);
        }
    	//将 p值（nums[lo]）交换到正确的位置
        swap(nums[lo], nums[j]);
        return j;
}

// 对数组元素进⾏随机打乱
void shuffle(vector<int>& nums) {
    random_shuffle(nums.begin(), nums.end());
}

快速选择

相关题目：

  1. 数组中的第 K 个最⼤元素（中等）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

解法：快排简化，可以在O(n) 时间复杂度，O(1) 空间复杂度完成求解工作。快速选择需要找到第k 大的枢（pivot），不需要对其左右再进行排序。快速选择一般需要先打乱数组，否则最坏情况下时间复杂度为O($n^2$).

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
//主函数
int findKthLargest(vector<int>& nums, int k) {
    	random_shuffle(nums.begin(), nums.end());// ⾸先随机打乱数组
        int l = 0, r = nums.size() - 1, target = nums.size() - k;
        while (l <= r) {
            int mid = quickSelection(nums, l, r);
            if (mid == target) {
                return nums[mid];
            }
            if (mid > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }

//辅助函数 - 快速选择
int quickSelection(vector<int>& nums, int l, int r) {
    int i = l + 1, j = r;
    while (true) {
        while (i < r && nums[i] <= nums[l]) {
            ++i;
        }
        while (l < j && nums[j] >= nums[l]) {
            --j;
        }
        if (i >= j) break;
        swap(nums[i], nums[j]);
    }
    swap(nums[l], nums[j]);
    return j;
}