快速排序

1.排序原理

任意取序列中的一个数据key值，分别从序列左右两边开始遍历，将小于key值的数据放在key值左边，将大于key的数据放在key值右边，于是我们得到一个以key值作为中间值的序列，然后我们利用递归思想在对key值左右俩个子序列分别重复以上操作，从而达到排序效果

<mark>排序过程如图</mark>

数组：num[5]={3,5,1,2,4}
key=3
i=0		{[3],5,1,2,[4]}		j=4	初始状态
i=0		{[3],5,1,[2],4}		j=3	右遍历,num[j]<key
i=0		{[2],5,1,[2],4}		j=3 右换位，num[i++]=num[j]
i=1		{2,[5],1,[2],4}		j=3 左遍历,num[i]>=key
i=1		{2,[5],1,[5],4}		j=3 左换位,num[j--]=num[i]
重复:
i=1		{2,[5],[1],5,4}		j=2 右遍历
i=1		{2,[1],[1],5,4}		j=2 换位，num[i++]=num[j]
i=2		{2,1,[[1]],5,4}		i=2	(i=j)跳过左遍历和左换位
结束循环，设置中间值：num[i]=key {2,1,3,5,4}

递归左右子序列：
左序列：{2,1}(key=2)		右序列{5,4}(key=5)
左序列					右序列
	重复....{1,2}			重复....{4,5}	
排序完成
{1,2,3,4,5}

2.源代码

#include<stdio.h>
#define N 10
void qsort(int num[],int L,int R)
{
	if(L<R)//递归结束条件
	{
		int i=L;//从数组左边开始遍历
		int j=R;//从数组右边开始遍历
		int key=num[L];//默认取数组第一个数为中间值
		while(i<j)
		{
			while(i<j&&num[j]>=key)//当num[j]就在key的右边
				j--;//向后遍历，直到i>=j或者num[j]<key时结束
			if(i<j)//以上while循环后如果i依然小于j，即num[j]<key
				num[i++]=num[j];//将num[j]放在左边
			while(i<j&&num[i]<key)//当num[i]在key的左边
				i++;//向前遍历
			if(i<j)//num[i]>=key
				num[j--]=num[i];//将num[i]放到右边
		}
		num[i]=key;//最后key作为中间值放在遍历结束的num[i]处
		qsort(num,L,i-1);//递归key值左边的子序列
		qsort(num,i+1,R);//递归key值右边的子序列
	}
}
int main()
{
	int num[N]={9,8,7,6,5,4,3,2,1,0};
	qsort(num,0,N-1);
	for(int i=0;i<N;i++)
		printf("%d",num[i]);
	printf("\n");
	return 0;
}