#include<stdio.h>

#define N 10

void swap(int *p1, int *p2);

void BubbleSort(int *a);

void SelectSort(int a[]);

void QuickSort(int *a, int left, int right);

int main(){

	int a[N] = {3,7,9,8,5,6,1,6,0,2};

	int i;

	//SelectSort(a);

	QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);

	for(i=0; i<N; i++){

	printf("%d ", a[i]);

	}

	return 0;

}

void swap(int *p1, int *p2){

	int temp = *p1;

	*p1 = *p2;

	*p2 = temp;

}

void swap2(int a[], int i, int j)

{

	int t = a[i];

	a[i] = a[j];

	a[j] = t;

}

void BubbleSort(int *a){  //大的向上升

	int i,j;

	for(i=0; i<N-1; i++){   /* 注意 N-1 */

		for(j=0; j<N-1-i; j++){

			if(a[j]>a[j+1])

				swap(&a[j],&a[j+1]);

		}

	}

}

void SelectSort(int a[]){  //最小的留在最下面

	int i,j,min;

	for(i=0; i<N-1; i++){    /*一个N-1,下面n*/

		min = i;

		for(j=i+1; j<N; j++){

			if(a[j]<a[min])

				min =j;

		}

		swap(&a[i],&a[min]);

	}

}

void QuickSort(int *a, int left, int right){

	int key = a[left];

	int i = left;

	int j = right;

	if(left >= right)

		return ;

	while(i<j){

		while(i<j && a[j]>=key){   /*a[j]>=key 如果只写> 会进入死循环*/

			j--;

		}

		a[i] = a[j];

		while(i<j && a[i]<=key){

			i++;

		}

		a[j] = a[i];

	}

	a[i] = key;   /*此时 i=j*/

	QuickSort(a, left, i-1);

	QuickSort(a, i+1, right);

}

/*

	    最差时间分析 平均时间复杂度  稳定度 空间复杂度

冒泡	 O(n2)			O(n2)         稳定	      O(1)

选择	 O(n2)			O(n2)         稳定	      O(1)

快速	 O(n2)			O(n*log2n)    不稳定      O(log2n)~O(n)

*/