#include<stdio.h>
#include<Windows.h>



//快速排序
int partion(int *arr,int low,int height){

	//快速排序的一个子模块
	
	int base = arr[low];//第一个元素开始
	int i = low;
	int j = height;

	if(low<height){
	while(i<j){
		//对第一个进行判断,第一个从右边的第j个开始找比base小的找不到的话j--
		while(i<j&&arr[j]>=base){
			j--;
		}

	//这是找到的情况
	if(i<j){
	//找到了让这个i这的下标位置存储这个j位置的元素
		arr[i++] = arr[j];

	}

	//对左边的第i个元素开始找比base大的元素

		
		while(i<j&&arr[i]<base){
			//找不到就让i++
			i++;
		}
		//这个是找到的情况
		if(i<j){
			//找到了的话
			arr[j--] = arr[i];
		
			}

		}
	
		arr[i] = base;
	}

	//排序结束之后就是low = height

	return i;
}

//归并算法
void GB(int *arr,int low,int height){
	//归并算法
	//递归的思想分而治之
	//那个return i为界限
	if(low<height){
		
		int index = partion(arr,low,height);//进行这么样的一个循环的作用是第一次排序找到163逮出来，然后对下面的进行处理

		GB(arr,low,index-1);
		GB(arr,index+1,height);


	}

	

}

int main(void){

	int arr[] = {163, 161, 158, 165, 171, 170, 163,159,162};
	int len = sizeof(arr)/sizeof(arr[0]);
	GB(arr,0,len-1);
	
	printf("快排完毕\n");
	
	for(int i=0;i<len;i++){
		
		printf("%d ",arr[i]);
	}

	printf("\n");



	

	system("pause");
	return 0;
	}