分治和归并
# 快速排序
| 阶段 | 快速排序的做法 |
|---|---|
| 分解 | 选择一个基准值（pivot），通过分区操作将数组分成三部分：[ < pivot ]、[ = pivot ]、[ > pivot ] |
| 解决 | 递归地对左右子区间（三路版中为 < pivot 和 > pivot 两部分）调用快速排序本身。等于 pivot 的元素已经就位，不再参与递归。 |
| 合并 | 无需显式合并。因为分区是原地完成的，当左右子区间都有序后，整个数组自然有序。这是快排与归并排序最大的区别。 |
// 三路快速排序
void qsort(vector<int>& nums, int left, int right) {
if(left >= right)
return;
int i = left, l = left - 1, r = right + 1;
int pivot = nums[rand() % (right - left + 1) + left];
while(i < r) {
if(nums[i] > pivot) swap(nums[--r], nums[i]);
else if(nums[i] == pivot) i++;
else swap(nums[++l], nums[i++]);
}
/*
[left, l]: < pivot
[l + 1, r - 1]: = pivot
[r, right]: > pivot
*/
qsort(nums, left, l);
qsort(nums, r, right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
例题：TopK 问题 215.数组中的第 K 个最大元素 (opens new window)
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
srand(time(NULL));
return qselect(nums, 0, nums.size() - 1, k);
}
// 快速选择算法：
int qselect(vector<int>& nums, int left, int right, int k) {
if (left == right)
return nums[left];
int i = left, l = left - 1, r = right + 1;
int pivot = nums[rand() % (right - left + 1) + left];
while (i < r) {
if (nums[i] > pivot)
swap(nums[--r], nums[i]);
else if (nums[i] == pivot)
i++;
else
swap(nums[++l], nums[i++]);
}
int c = right - r + 1, b = r - l - 1;
if (c >= k) {
return qselect(nums, r, right, k);
} else if (c + b >= k) {
return pivot;
} else {
return qselect(nums, left, l, k - b - c);
}
}
};
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
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
# 归并排序
| 阶段 | 归并排序的做法 |
|---|---|
| 分解 | 将数组从中间位置一分为二，得到两个规模相等的子数组：[left, mid] 和 [mid+1, right] |
| 解决 | 递归地对左右子数组分别调用归并排序，直到子数组长度为 1（天然有序） |
| 合并 | 将两个已排序的子数组合并成一个完整的有序数组，这是归并排序的核心步骤，需要 O(n) 的辅助空间 |
void mergeSort(vector<int>& nums, int left, int right) {
if (left >= right)
return;
// 1. 划分左右区间
int mid = (right - left) / 2 + left;
// 2. 左右区间排序
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 3. 还原数组
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right)
temp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
while (cur1 <= mid)
temp[i++] = nums[cur1++];
while (cur2 <= right)
temp[i++] = nums[cur2++];
for (int i = left; i <= right; ++i)
nums[i] = temp[i - left];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
利用归并排序思想，核心就是在合并两个有序子数组时，利用有序性来快速计算某种跨左右子数组的统计量。
class Solution {
public:
vector<int> temp;
int ret = 0;
int reversePairs(vector<int>& record) {
temp.resize(record.size());
mergeSort(record, 0, record.size() - 1);
return ret;
}
void mergeSort(vector<int>& nums, int left, int right) {
if (left >= right)
return;
// 1. 划分左右区间
int mid = (right - left) / 2 + left;
// 2. 左右区间排序
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 3. 还原数组，计算逆序对：
int cur1 = left, cur2 = mid + 1, i = 0;
// 升序：
// while (cur1 <= mid && cur2 <= right) {
// if (nums[cur1] <= nums[cur2]) {
// temp[i++] = nums[cur1++];
// } else {
// ret += mid - cur1 + 1;
// temp[i++] = nums[cur2++];
// }
// }
// 降序：
// while (cur1 <= mid && cur2 <= right) {
// if (nums[cur1] <= nums[cur2]) {
// temp[i++] = nums[cur2++];
// } else {
// ret += right - cur2 + 1;
// temp[i++] = nums[cur1++];
// }
// }
while (cur1 <= mid)
temp[i++] = nums[cur1++];
while (cur2 <= right)
temp[i++] = nums[cur2++];
for (int i = left; i <= right; ++i)
nums[i] = temp[i - left];
}
};
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
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
LCR 170. 交易逆序对的总数
- 计算右侧小于当前元素的个数
todo
上次更新: 2026/04/29, 15:44:34
