快排

归并排序是稳定算法（也就是说， 在值相等的情况下， 它们两个的顺序保持不变）， 归并排序时， 在要将两个分开的数据合起来的时候， 要注意， 它选择开辟一个新的空间， 然后实现

快排思想：排序数据下标从a-p, 那么选择a-p之间的任意数据作为分区点， 将小于分区点的值放到左边， 大于分区点的值放到右边
快排的最坏情况时间复杂度是n^2, 最好是n, 平均是n*log(n)
快排的具体思想：
每一次分区也就是调用patition方法， 就确定一个数据的具***置， 在它的左边都是比它小的， 在它的右边都是比她大的

关键代码：

int partition(vector<int> &vec,int low,int high){ //传入的值是low和high， 而返回的值是vec[low]的值实际应该待的位置
int temp = vec[low]; //保存了low的值， 所以， 第一次用low的位置当作空闲位置， 当哨兵
while(low<high){ //一个大的循环
while(low<high && vec[high]>=temp){ //找到一个循环里， 第一个遇到的比vec[low]小的值， 把他放在low里面
high--;
}
vec[low]=vec[high]; //这里保存了high的值， 所以用high的位置当作空闲位置， 把他放到high里面
while(low<high && vec[low]<=temp){ //找到一个循环里， 第一个遇到的比它大值， 把它放到high里面
low++;
}
vec[high]=vec[low];
}
vec[low]=temp; //放好初始vec[low]应该放的位置
return low; //返回low最终的放置位置
}</int>

具体快排列调用：

int quicksort(vector<int> &vec,int low,int high){
if(low<high){
int mid = partition(vec,low,high); //将low位置的元素放到正确位置, 并返回low的正确位置值
quicksort(vec,low,mid-1); //排mid之前的数据
quicksort(vec,mid+1,high); //排mid之后的数据
}
}</int>

main函数里面：

int main(){
int len=20;
vector<int> vec;
for(int i=0;i<len;i++){
vec.push_back(rand());
}
quicksort(vec,0,len-1); //排序
for(int i=0;i<len;i++){
cout<<vec[i]<<endl;
}
}</int>