#include<iostream>
using namespace std;

///快排，百度数据挖掘，我面到终面
///他们部门经理过来面我
///数据挖掘的东西，兵来将挡，水来土掩
////讲完项目于对互联网的理解
///他说，最后写个快排吧~~~~
////FUCK，我没写出来
////嚓嚓嚓嚓嚓
int AdjustArray(int* a,int l,int r)
{
    int x = a[l];
    while(l<r)
    {
     while(l<r && a[r] >= x) r--;
     if(l<r)
     {
      a[l] = a[r];
      l++;
     }
     while(l<r && a[l] < x) l++;
     if(l<r)
     {
         a[r] = a[l];
         r--;
     }
    }
    a[l] = x;
    return l;
}

void quicksort(int* a,int l,int r)
{
    if(l < r)
    {
     int i = AdjustArray(a,l,r);
     quicksort(a,l,i-1);
     quicksort(a,i+1,r); ///分清左右
    }
}

int main()
{
    int a[] = {1,9,5,3,7,2,6,3,4};
    quicksort(a,0,8);
    for(int i = 0;i< 8;i++)
        cout<<a[i]<<" ";
}