快速排序
虽然可以直接用std::sort函数混过去，但快速排序作为计算机考研初试专业课热点，了解原理很有必要
快速排序基于递归与分治思想，先将序列划分为相对有序的两部分，然后分别对两部分继续排序。和大多数递归分治算法一样，原理很简单但实现起来不容易，话不多说，上图！
图中展示的就是第一轮排序的划分情况，取序列中值45为枢值(pivotKey)，然后让首尾索引low和high向中间靠拢，当arr[low]>=pivotKey或者arr[high]<=pivotKey时停止，此时如果两索引尚未相遇，则交换两索引对应位置的值，交换过后不在原地停留，而是继续按相同方向前往下一个位置。这部分过程定义和考研408数据结构不一样，如果按照408数据结构的方式，取一端的值为枢值，那么在划分的每一次循环时，必有一个索引是原地不动的（这里可以自己画图模拟，如果已经考过了应该不会陌生的），这样会增加一倍的交换次数，而取中值为枢值就可以同时移动两个索引
划分结束后，左右两边以high索引为分界线，分成了相对有序的两部分，左半区的值全部小于枢值，右半区的值全部不小于枢值，但是区段内部仍然是无序的，此时就要对两部分分别进行划分和排序，直到无法再划分
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
void quickSort(int* arr, int left, int right) {
if(left >= right) return;
//取中值为枢值
int mid = (left + right) / 2, pivotKey = arr[mid];
int low = left - 1, high = right + 1;
//划分时是先比较后移动
while(low < high) {
do {
low++;
} while(arr[low] < pivotKey);
do {
high--;
} while(arr[high] > pivotKey);
//对应找到了左/右部分大/小于枢值的元素，索引还未相遇就交换
if(low < high) {
swap(arr[low], arr[high]);
}
}
//此时已经保证相对有序
quickSort(arr, left, high);
quickSort(arr, high + 1, right);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int* arr = new int[n];
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
quickSort(arr, 0, n - 1);
for(int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
delete[] arr;
return 0;
}
