?? 快速排序,说白了就是给基准数据找其正确索引位置的过程.
?? 如下图所示,假设最开始的基准数据为数组第一个元素23,则首先用一个临时变量去存储基准数据,即tmp=23;然后分别从数组的两端扫描数组，设两个指示标志:low指向起始位置，high指向末尾.
?? 首先从后半部分开始，如果扫描到的值大于基准数据就让high减1,如果发现有元素比该基准数据的值小(如上图中18<=tmp)，就将high位置的值赋值给low位置 ,结果如下:
然后开始从前往后扫描,如果扫描到的值小于基准数据就让low加1,如果发现有元素大于基准数据的值(如上图46=>tmp)，就再将low位置的值赋值给high位置的值,指针移动并且数据交换后的结果如下:
然后再开始从后向前扫描,原理同上,发现上图11<=tmp,则将low位置的值赋值给high位置的值 ,结果如下:
然后再开始从后向前扫描,原理同上,发现上图11<=tmp,则将high位置的值赋值给low位置的值,结果如下:
然后再开始从前往后遍历,直到low=high结束循环,此时low或high的下标就是基准数据23在该数组中的正确索引位置.如下图所示.
??这样一遍走下来,可以很清楚的知道,其实快速排序的本质就是把基准数大的都放在基准数的右边,把比基准数小的放在基准数的左边,这样就找到了该数据在数组中的正确位置.
??以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了
1 /*** 2 * @Description: one new start! 3 * @version: 4 * @Author: MocWangYu 5 * @Date: 2020-10-22 10:46:30 6 * @LastEditors: MocWangYu 7 * @LastEditTime: 2020-10-29 11:28:21 8 */ 9 #include<iostream> 10 using namespace std; 11 12 void disp(int a[],int n)//输出a[] 13 { 14 int i; 15 for(i=0;i<n;i++){ 16 cout<<a[i]<<" "; 17 }cout<<endl; 18 } 19 int Partition(int a[],int low,int high) 20 { 21 int i=low,j=high; 22 int tmp=a[low]; 23 while(i!=j) 24 { 25 while (j>i&&a[j]>=tmp) 26 { 27 j--; 28 }a[i]=a[j]; 29 while (i<j&&a[i]<=tmp) 30 { 31 i++; 32 }a[j]=a[i]; 33 }a[i]=tmp; 34 return i; 35 } 36 void QuickSort(int a[],int low,int high) 37 { 38 if(low<high) 39 { 40 int i=Partition(a,low,high); 41 QuickSort(a,low,i-1); 42 QuickSort(a,i+1,high); 43 } 44 } 45 int main() 46 { 47 int a[]={23,16,0,8,11,18}; 48 int n=sizeof(a)/sizeof(a[0]); 49 cout<<"排序前："; 50 disp(a,n); 51 QuickSort(a,0,n-1); 52 cout<<"排序后："; 53 disp(a,n); 54 return 0; 55 }
原文：https://www.cnblogs.com/nuistwangyu/p/13895837.html
