#include <iostream>
using namespace std;
//挖坑填坑，分治

//挖坑填坑
//分
void mySwap(int &a,int &b){
    int tmp = a;
    a = b;
    b = tmp;
}

int partition(int start,int end,int a[]){
    //去中间为基准，将它与第一个元素交换
    //swap(a[start], a[(start+end)/2]);
    int i = start;
    int j = end;
    int x = a[start];
    while (i<j) {
        while (i<j&&a[j]>=x) {
            j--;
        }
        if (i<j) {
            //挖坑填坑
            a[i] = a[j];
            i++;
        }
        while (i<j&&a[i]<x) {
            i++;
        }
        if (i<j) {
            a[j] = a[i];
            j--;
        }
    }
    a[i] = x;
    return i;
}

//治
void quickSort(int low,int high,int a[]){
    if (low<high) {
        int p = partition(low, high, a);
        quickSort(low, p-1, a);
        quickSort(p+1, high, a);
    }
}


void QuickSort(int n,int a[]){
    quickSort(0, n-1, a);
}

int main(int argc, const char * argv[]) {
    int a[] = {1,4,2,8,7,9,6};
    QuickSort(7, a);
    for (int i=0; i<7; i++) {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}