#include<iostream>
using namespace std;

/*交换*/ 
void swap(int *x,int *y){
	int temp;
	temp=*x;
	*x=*y;
	*y=temp;
}

/*打印*/ 
void print(int *a,int length){
	int i;
	for(i=0;i<length;i++)
		cout << *(a+i) << " ";
	cout<<endl;
}

/*起泡排序*/
void sort_bubble(int *a,int length){
	int i,j;
	for(i=0;i<length-1;i++){//外层循环，控制循环比较趟数 
		for(j=0;j<length-1-i;j++){//内层循环，控制比较位置 
			if(*(a+j)>*(a+j+1))//判断是否符合交换规则 
				swap(a+j,a+j+1);
		}
	} 
	print(a,length);
}

/*选择排序*/
void sort_select(int *a,int length){
	int i,j,k;
	for(i=0;i<length-1;i++){//外层循环，控制每一趟起始位置 
		for(j=i+1;j<length;j++){//内层循环，控制每趟循环比较次数 
			if(*(a+i)>*(a+j))//判断是否符合交换规则 
				swap(a+i,a+j);
		}
	} 
	print(a,length);
}

/*归并排序细节*/
void merge(int *a,int first,int middle,int last){
	int n=0;
	int i=first,j=middle+1; 
	int b[last+1];//数组b暂存排好序的元素 
	while(i<=middle&&j<=last){
		if(a[i]<a[j])
			b[n++]=a[i++];
		else
			b[n++]=a[j++];
	}
	while(i<=middle)
		b[n++]=a[i++];
	while(j<=last)
		b[n++]=a[j++];

	int k;
	for(k=first;k<first+n;k++)//难点、易错点 
		a[k]=b[k-first]; 
}

/*归并排序主体*/
void mergesort(int *a,int first,int last){
	if(first<last){
		int middle=(first+last)/2;
		mergesort(a,first,middle);
		mergesort(a,middle+1,last);
		merge(a,first,middle,last);
	}
}  

/*归并排序*/
void sort_merge(int *a,int first,int last){
	mergesort(a,first,last);
	print(a,last+1);
}  

/*快速排序细节*/
void quicksort(int *a,int low,int high){
	int first=low;
    int last=high;
    int key=a[low];//哨兵 
    if(low>=high)//如果low>=high说明排序结束了
        return;
    while(low<high){//该while循环结束一次表示比较了一轮
        while(low<high&&key<=a[high])
            --high;//向前寻找
        if(key>a[high]){
            swap(&a[low],&a[high]);
            ++low;
        }
        while(low<high&&key>=a[low])
            ++low;//向后寻找
        if(key<a[low]){
            swap(&a[low],&a[high]);
            --high;
        }
    }
    quicksort(a,first,low-1);  //用同样的方式对分出来的左边的部分进行同上的做法
    quicksort(a,low+1,last);  //用同样的方式对分出来的右边的部分进行同上的做法
}

/*快速排序*/
void sort_quick(int *a,int low,int high){
	quicksort(a,low,high);
	print(a,high+1);
}

/*主函数*/ 
int main(){

	int a[]={62,41,51,99,79,13,54,53,30,73};
	
	int i,j,length;
	
	length=sizeof(a)/sizeof(a[0]);
	
	//sort_bubble(a,length);
	//sort_select(a,length);
	//sort_merge(a,0,length-1);
	sort_quick(a,0,length-1);

	return 0;
}