AcWing 785. 快速排序
原题链接
简单
作者:
owonder
,
2020-08-30 02:06:15
,
所有人可见
,
阅读 391
C++ 代码
#include<vector>
#include<iostream>
using namespace std;
int Partition(vector<int> &data,int left,int right){
int middle=data[left]>data[right]?right:left;
while(left<right){
while(left<right&&data[right]>=data[middle]) right--;
while(left<right&&data[left]<=data[middle]) left++;
if(left<right){
swap(data[left],data[right]);
}
}
//这个是因为left比right大,说明此时left肯定要比middle大了
swap(data[left],data[middle]);
return left;
}
void QuickSort(vector<int>& data,int left,int right){
if(left>=right){
return ;
}
int middle=Partition(data, left, right);
QuickSort(data, left,middle-1);
QuickSort(data, middle+1,right);
}
int main(){
vector<int> datas={1,5,6,2,3,4};
QuickSort(datas,0,datas.size());
for(const auto& it: datas){
cout<<it<<endl;
}
}