要求根据给定输入，按照课堂给定的快速排序算法进行排序，输出排序结果和median3的返回值。

 注：1,cutoff值为5，不足cutoff使用插入排序。

        2,输入、输出格式参见测试用例0。

测试输入期待的输出时间限制内存限制额外进程测试用例 1以文本方式显示

1. 41↵
2. 17↵
3. 34↵
4. 0↵
5. 19↵
6. #↵

以文本方式显示

1. After Sorting:↵
2. 0 17 19 34 41 ↵
3. Median3 Value:↵
4. none↵

1秒64M0测试用例 2以文本方式显示

1. 61↵
2. 59↵
3. 82↵
4. -10↵
5. 31↵
6. -2↵
7. -3↵
8. 10↵
9. 2↵
10. 108↵
11. 12↵
12. 80↵
13. -21↵
14. 127↵
15. 12↵
16. #↵

以文本方式显示

1. After Sorting:↵
2. -21 -10 -3 -2 2 10 12 12 31 59 61 80 82 108 127 ↵
3. Median3 Value:↵
4. 12 -3 61 ↵

1秒64M0

C++代码

#include<iostream> 
#include<algorithm> 
#include<vector> 
using namespace std;const int cutoff = 5;
vector<int> median;// 插入排序 
void insertionSort(vector<int>& arr, int left, int right) {for (int i = left + 1; i <= right; i++) {int tmp = arr[i], j = i;for (; j > left && arr[j - 1] > tmp; j--)arr[j] = arr[j - 1];arr[j] = tmp;}
}// 计算中位数 
void median3(vector<int>& arr, int left, int right) {int center = (left + right) / 2;if (arr[left] > arr[center])swap(arr[left], arr[center]);if (arr[left] > arr[right])swap(arr[left], arr[right]);if (arr[center] > arr[right])swap(arr[center], arr[right]);//将中位数放到right-1位置作为枢纽元 swap(arr[center], arr[right - 1]);
}// 快速排序 
void quickSort(vector<int>& arr, int left, int right) {if (right - left + 1 <= cutoff) {insertionSort(arr, left, right);return;}median3(arr, left, right);median.push_back(arr[right - 1]); int i = left, j = right - 1;int pivot = arr[right - 1];for (;;) {while (arr[++i] < pivot) {}while (arr[--j] > pivot) {}if (i < j)swap(arr[i], arr[j]);elsebreak;}swap(arr[i], arr[right - 1]);quickSort(arr, left, i - 1);quickSort(arr, i + 1, right);
}// 主函数处理输入输出 
int main() {int num;vector<int> nums;while (cin >> num && cin.peek() != '#') {nums.push_back(num);}quickSort(nums, 0, nums.size() - 1);cout << "After Sorting:" << endl;for (const auto& n : nums) {cout << n << " ";}cout << endl;cout << "Median3 Value:" << endl;if (nums.size() > 5) {for (int i = 0; i < median.size(); i++) {cout << median[i] << " ";}}else cout << "none";cout << endl;return 0;
}