/*
* 快速排序
* 值分界点
* 调整区间<=x >=x
* 递归
*
*/
#include <iostream>
#include <vector>
using namespace std;
void quick_sort(vector<int> &nums, int l, int r) {
if (l >= r) return;
// 值分界点
int x = nums[(l + r) / 2];
// 调整区间,双指针,分别从头尾相向而行,交换不满足区间要求的数
// 区间:<x >x
int i = l - 1, j = r + 1;
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j) swap(nums[i], nums[j]);
}
// 递归
quick_sort(nums, l, j);
quick_sort(nums, j + 1, r);
}
/*
* 终止条件
* 分界点 mid = (l+r)/2
* 分段递归
* 归并(需要额外的数组,i,j,k)
*/
void merge_sort(vector<int> &nums, int l, int r) {
// 终止条件
if (l >= r) return;
// 分界点
int mid = (l + r) / 2;
// 分段递归
merge_sort(nums, l, mid);
merge_sort(nums, mid + 1, r);
// 归并
vector<int> tmp(r - l + 1); // 缓冲区
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
else tmp[k++] = nums[j++];
}
// 剩余的数
while (i <= mid) tmp[k++] = nums[i++];
while (j <= r) tmp[k++] = nums[j++];
// 拷贝回原数组
for (int i = l, k = 0; i <= r; i++, k++) nums[i] = tmp[k];
}
int main() {
vector<int> nums{8, 2, 4, 6, 2, 9, 1};
// quick_sort(nums, 0, nums.size()-1);
merge_sort(nums, 0, nums.size() - 1);
for (int x: nums) cout << x << " ";
cout << endl;
return 0;
}