🏷️ 知识点：快速排序的单向递归算法
2016 年第 43 题
组成原理
综合题
已知由n(n≥2)个正整数构成的集合A=ak∣0≤k<n，将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足∣n1−n2∣最小且∣S1−S2∣最大。要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。
1）算法的基本设计思想由题意知，将最小的⌊n/2⌋个元素放在A1中，其余的元素放在A2中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理：
- 若i=⌊n/2⌋，则分组完成，算法结束；
- 若i<⌊n/2⌋，则枢轴及之前的所有元素均属于A1,继续对 i 之后的元素进行划分；
- 若i>⌊n/2⌋，则枢轴及之后的所有元素均属于A2，继续对i之前的元素进行划分；基于该设计思想实现的算法，无须对全部元素进行全排序，其平均时间复杂度是O(n)，空间复杂度是O(1)。
2）算法实现实现
[tag_link]
参考 快速排序的单向递归算法。
int partition(int a[], int low, int high) {
int l = low;
int r = high;
int pivot = a[l];
while (l < r) {
while (l < r && a[r] >= pivot) {
r--;
}
a[l] = a[r];
while (l < r && a[l] <= pivot) {
l++;
}
a[r] = a[l];
}
a[l] = pivot;
return l;
}
// 按照第 k 个元素进行分区
void quickSelect(int a[], int low, int high, int k) {
if (low < high) {
int pivotIndex = partition(a, low, high);
if (pivotIndex == k) {
return
} else if (pivotIndex < k) {
quickSelect(a, pivotIndex+1, high, k);
} else {
quickSelect(a, low, pivotIndex-1, k);
}
}
}
// 空间复杂度：O(1)
// 时间复杂度：O(n)
void solve(int a[], int n) {
quickSelect(a, 0, n-1, n/2);
int S1 = 0;
int S2 = 0;
for (int i = 0; i < n/2; i++) {
S1 += a[i];
}
for (int i = n/2; i < n; i++) {
S2 += a[i];
}
return S2 - S1;
}
3）本参考答案给出的算法平均时间复杂度是O(n), 空间复杂度是O(1)。