具体的思想是将一个数字放到正确的位置上（排序后应该在的位置），同时将其他数字也都放到近似正确的位置上，用例子来说明是最好的，下图将56放到正确的位置上，然后把比它小的都放在它左边，比它大的都放在它右边。
程序如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include<set>#include<vector>#include<iostream>using namespace std;int find_middle(vector<int>& nums,int left,int right){ int i=left,j=right; int middle_value=nums[i]; while(i<j){ for(;i<j;j--){ if(nums[j]<middle_value){ nums[i]=nums[j]; break; } } for(;i<j;i++){ if(nums[i]>middle_value){ nums[j]=nums[i]; break; } } } nums[i]=middle_value; return i;}void quick_sort(vector<int>& nums,int left,int right){ if(left==right) return; else{ int middle=find_middle(nums,left,right); if(left<middle) quick_sort(nums,left,middle-1); if(middle<right) quick_sort(nums,middle+1,right); } }int main(){ int a[10]={1,3,5,7,9,2,4,6,8,10}; vector<int> vi(a,a+10); for(int i=0;i<vi.size();i++) cout<<vi[i]<<" "; cout<<endl; quick_sort(vi,0,9); for(int i=0;i<vi.size();i++) cout<<vi[i]<<" "; cout<<endl;} |