要点：
- 归并排序 和 快速排序的实现
代码：
#include <iostream>
#include <vector>
using namespace std;
//快排
void quick_sort(vector<int>& nums, int left, int right) {
if (left < right) {
int low = left;
int high = right;
int x = nums[left];
while (low < high) {
while (low < high && nums[high] >= x) high--;
if (low < high) nums[low++] = nums[high];
while (low < high && nums[low] <= x) low++;
if (low < high) nums[high--] = nums[low];
}
nums[low] = x;
quick_sort(nums, left, low - 1);
quick_sort(nums, low + 1, right);
}
}
void merge(vector<int>& nums, int left, int mid, int right) {
vector<int> tmp(right - left + 1);
int k = 0;
int i = left;
int j = mid + 1;
while (i <= mid && j <= right) {
if (nums[i] < nums[j]) {
tmp[k++] = nums[i++];
}
else {
tmp[k++] = nums[j++];
}
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
for (int i = 0; i < tmp.size(); i++) {
nums[left + i] = tmp[i];
}
}
//归并排序
void merge_sort(vector<int>& nums, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
merge_sort(nums, left, mid);
merge_sort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
void print_vec(vector<int>& nums) {
int len = nums.size();
for (int i = 0; i < len; i++) {
if (i == len - 1) {
cout << nums[i] << endl;
}
else {
cout << nums[i] << ' ';
}
}
}
int main() {
vector<int> nums;
int n;
while (cin >> n) {
nums.push_back(n);
if (getchar() == '\n') {
break;
}
}
print_vec(nums);
quick_sort(nums,0,nums.size()-1);
print_vec(nums);
return 0;
}