题解 | C++#易懂的快速排序#

void quick(vector<int>&arr,int low,int high)
{
if(arr.size()==0||arr.empty())return;
if(low>=high)return;//如果low>high，显然非法；如果只传了一个数，因此low==high，就不用排序了，因此return
int key = arr[low];//设定一个基准值，可以是arr[low]也可以是arr[high]
int l = low;//左边界
int r = high;//右边界
while(l!=r)//左右两个指针开始搜索，直到它们重合
{
//注意这里一定要先r，再l，否则一定出错
//left(→)负责找大于key数，right(←)负责找小于key数
while(arr[r]>=key && l<r){//找到就停下，没找到继续
r--;
}
while(arr[l]<=key && l<r){//找到就停下，没找到继续
l++;
}
swap(arr[l], arr[r]); //都找到了，交换（如果都没找到也能够执行到此步，此时就相当于数跟本身交换，不影响）
}
arr[low] = arr[l];
arr[l] = key;//这里用l或者r都可以，因为此时l==r
//运行到这里，数列是这样的 a,b,c,l,d,e,f，因此还要分别处理l两边的数列：
quick(arr, low,l-1);//左边递归，传边界
quick(arr, l+1, high);//右边递归，传边界
}
vector<int> MySort(vector<int>& arr) {
// write code here
quick(arr,0,arr.size()-1);
return arr;
}</int></int></int>