快速排序

快速排序使用分治策略来把待排序数据序列分为两个子序列，具体步骤为：

（1）从数列中挑出一个元素，称该元素为“基准”。
（2）扫描一遍数列，将所有比“基准”小的元素排在基准前面，所有比“基准”大的元素排在基准后面。
（3）通过递归，将各子序列划分为更小的序列，直到把小于基准值元素的子数列和大于基准值元素的子数列排序。

# include <iostream>

using namespace std;

void QuickSort(int *a,int low,int high);
int Find(int *a,int low,int high);
int main(){
  
  int a[]={1,69,-5,26,-18883,-56};
  
  QuickSort(a,0,5);
  
  for(int i=0;i<6;i++){
    cout<<a[i]<<"   ";
  } 
  
  return 0;
}

void QuickSort(int *a,int low,int high){
  //high必须大于low，递归的结束条件 
  
  int pos; 
  if(low<high){
    pos = Find(a,low,high);//查找每一次排过序的位置
    QuickSort(a,low,pos-1);//左边找位置 
    QuickSort(a,pos+1,high);//右边找位置  
  }
  
}

int Find(int *a,int low,int high){

  int val = a[low];//每一组的最小的数,最为基数 
  while(low<high){
    //在刚开始,移动右边的数
    //while循环的目的//查找比第一个元素小的 
    while(low<high && a[high]>=val){//碰见比val大的就不跳出while,直到找到你val小的,跳出循环 
      high--;
    } 
    a[low] = a[high];//小的数赋值给a[low] 这是high的下标不动,开始移动low的下标 
    
    //while循环的目的 查找比val大等于的元素
    while(low<high && a[low]<val){
      low++;
    } 
    a[high] = a[low];
  }//此循环结束low与high相等 
  
  a[low] = val;
 
  return  low;//把low改成high一样
 }

# include <iostream>
using namespace std;


int Find(int a[], int low, int high) {

    int val = a[low];
    while (low < high) {
        while(low<high && val<=a[high]) {
            high--;
        }
        a[low] = a[high];
        while(low<high && val>a[low]) {
            low++;
        }
        a[high] = a[low];
    }
    a[low] = val;
    return low;
}


void sortQuick(int a[], int low, int high) {
    if(low < high) {
        int position = Find(a, low, high);
        sortQuick(a, low, position-1);
        sortQuick(a, position+1, high);
    }

}

int main() {

    int a[] = {1,69,-5,26,-18883,-56};
    int len = sizeof(a)/sizeof(a[0]);

    sortQuick(a, 0, len-1);
    
    for(int i=0;i<len;i++) {
        cout<<a[i]<<" ";
    }

    cout<<endl;

    return 0;
}