快速排序——递归算法
处理i,j的先后顺序不能改变
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
函数：
partition()函数实现了根据数组第一个元素区分这个数组，比这个元素小的放到mid的前面，比这个元素大的放到mid的后面
quicksort()函数：实现了递归调用
#include<iostream>#include<bits/stdc++.h>using namespace std;vector<int> vec;int partition(vector<int> &vec,int left,int right);void QuickSort(vector<int> &vec,int left,int right){if(left<right){int mid = partition(vec, left, right);QuickSort(vec, left, mid-1);QuickSort(vec, mid + 1, right);}}int partition(vector<int> &vec,int left,int right){int i=left, j=right;int temp = vec[left];while(i<j){while(temp<=vec[j]&&i<j)//处理i,j的先后顺序不能改变 {j--;}while(vec[i]<=temp&&i<j)//处理i,j的先后顺序不能改变 {i++; }swap(vec[i],vec[j]);}vec[left] = vec[j];vec[j] = temp;return j;}int main(){vector<int> vec={6,1,2,7,9,3,4,5,10,8};cout<<"排序前的序列：";for (auto a:vec){cout << a<<" ";}cout<<endl<<"排序后的序列：";int count = vec.size()-1;QuickSort(vec, 0, count);for (auto a:vec){cout << a<<" ";}cout<<endl;system("pause");return 0;}
如果觉得《算法设计与分析——递归与分治策略——快速排序》对你有帮助，请点赞、收藏，并留下你的观点哦！
