#include <iostream>
using namespace std;

int partition(int start, int end, int arr[])
{
	//从a[start..end]中选取一个pivot元素（比如选a[start]为pivot）;
	int pivot=arr[start];
	int l=start,r=end;
	
	while(l<r)
	{
		while(l<r && arr[r]>=pivot)
			r--;
		if(l<r)
		{
			arr[l]=arr[r];
			l++;
		}
		
		while(l<r && arr[l]<pivot)
			l++;
		if(l<r)
		{
			arr[r]=arr[l];
			r--;
		}
		
	}
	arr[l]=pivot;
	return l;
}

void quickSort(int start, int end, int arr[])
{
	int mid;
	if (end > start) {
		mid = partition(start, end ,arr);
		quickSort(start, mid-1, arr);
		quickSort(mid+1, end, arr);
	}
}

int main(int argc, char* argv[])
{
	int arr[]={10,5,4,2,3,1,8};
	int len=7;
	quickSort(0,len-1,arr);
	for(int i=0;i<len;i++)
		cout<<arr[i]<<" ";
	cout<<endl;
	return 0;
}