学步园

快速排序是不稳定的排序，但是算法复杂度低，平均算法复杂度为：O(nlgn)，最差为O(n^2)。空间复杂度为：O(lgn)

#include<stdio.h>

int PARTITION(int a[],int i,int j)
{
	int key=a[i];	//记录关键字

	while(i<j)
	{
		while(i<j && key<=a[j])		//向右扫描
			j--;
						//此时的j为key的位置
		if(i<j)
			a[i++]=a[j];	//交换位置

		while(i<j && key>=a[i])
			i++;
						//此时的i为key的位置
		if(i<j)
			a[j--]=a[i];	//交换位置
	}
	a[i]=key;	//key最终的位置
	return i;
}

void qsort(int a[],int i,int j)
{
	int pos;	//关键字的位置

	if(i<j)
	{
		pos=PARTITION(a,i,j);
		qsort(a,i,pos-1);
		qsort(a,pos+1,j);
	}
}

void main()
{
	int a[10]={7,17,6,84,56,1,34,10,100,0};

	qsort(a,0,9);	//快速排序
	
	for(int i=0;i<10;i++)
	{
		printf("%d\n",a[i]);
	}
}