蓝桥杯算法提高-快速排序

解题思路:

注意事项:
快排时，先从右向左找小于基准值的数交换，再从左向右找大于基准数的值交换。
参考代码:

#include <iostream>
using namespace std;
void QuickSort(int *array,int low,int high);
int main() {
   int a[10],n=0;
   while(cin>>a[n]&&a[n]!=0){
       n++;
   }
   QuickSort(a,0,n-1);//high一定是数组的长度-1
   for (int i = 0; i < n; ++i) {
       cout<<a[i]<<" ";
   }
   return 0;
}
void QuickSort(int *array,int low,int high){   //快排
   if(low>=high){ //若待排序序列只有一个元素，返回空
       return ;
   }
   int i=low; //i作为指针从左向右扫描
   int j=high;    //j作为指针从右向左扫描
   int key=array[low];//第一个数作为基准数 //
   while(i<j){
       while(array[j]>=key&&i<j){ //从右边找小于基准数的元素 （此处由于j值可能会变，所以仍需判断i是否小于j）
           j--;   //找不到则j减一
       }
       //cout<<"array[i]:"<<array[i]<<" array[j]:"<<array[j]<<" i:"<<i<<" j:"<<j<<endl;
       array[i]=array[j]; //找到则赋值 这里可以这样交换的原因是key=array[low],
                           //如果还不理解就在这句的上下各加一句cout，自己再画图理解
       //cout<<"array[i]:"<<array[i]<<" array[j]:"<<array[j]<<" i:"<<i<<" j:"<<j<<endl;
       while(array[i]<=key&&i<j){ //从左边找大于基准数的元素
           i++;   //找不到则i加一
       }
       //cout<<"*******"<<"array[i]:"<<array[i]<<" array[j]:"<<array[j]<<" i:"<<i<<" j:"<<j<<endl;
       array[j]=array[i]; //找到则赋值 同上
       //cout<<"*******"<<"array[i]:"<<array[i]<<" array[j]:"<<array[j]<<" i:"<<i<<" j:"<<j<<endl;
   }
   array[i]=key;  //当i和j相遇，将基准元素赋值到指针i处
   QuickSort(array,low,i-1);  //i左边的序列继续递归调用快排
   QuickSort(array,i+1,high); //i右边的序列继续递归调用快排
}