排序算法——快速排序

排序算法原理：

1. 在要排序的数据中以第一个为基数
2. 在这个数的左边都放比它小的数，右边都放比它大的数
3. 在以这个基数为界分成的左边数据和右边数据分别重复1，2步骤

以5  10  4  7  6   3  8  9  20  1为例进行快速排序

第一步：选择5为基数

第二步: 

1. 设两个指针分别为left指向第一个数即基数，right指向最后一个数，mid=5;
2. right向前遍历直到遇到的数小于基数5，并且不与left相遇；此时将right指向的数赋给left； 
3. left向后遍历直到遇到的数大于基数5，并且不与right相遇；此时将left指向的数赋给right；

第三步：重复第一步，第二步；

代码实现：

#include <stdio.h>
#define MAXSIZE 100
int func(int *p,int len)		//基数调整函数，返回调整完后基数的位置
{
	int left=0;			//p[left]为左指针指向数
	int right=len-1;	        //p[right]为右指针指向数
	int mid=p[0];			//基数为p[0]
	
	while(left<right)		//left与right相遇则调整完毕结束循环
	{
		while(p[right]>=mid && right>left)	//当p[right]小于mid或者right与left相遇结束循环
		{
			right--;			//right向前遍历
		}
		p[left]=p[right];		        //发现比基数小的数，放到基数的左边
		
		while(p[left]<=mid && right>left)        //当p[left]大于mid或者right与left相遇结束循环
		{
			left++;				//left向后遍历
		}
		p[right]=p[left];			//发现比基数大的数，放到基数的右边
	}
	p[left]=mid;					//保存基数
	return left;					//返回基数的位置
}


void Quick_sort(int *p,int len)		//快速排序
{
	if(len<2)			//数组的长度小于2时不用排序
	{
		return ;
	}	
	int ret;
	ret=func(p,len);		//第一次基数调整，返回基数所在位置
	Quick_sort(p,ret);		//对基数左边的数组进行基数调整,递归调用Quick_sort();
	Quick_sort(p+ret+1,len-ret-1);	//对基数右边的数组进行基数调整,递归调用Quick_sort();
}

void print(int *p,int len)		//打印数组
{
	int i;
	for(i=0;i<len;i++)
		printf("%d ",p[i]);
	printf("\n");
}

int main()
{
	int len=0;
	char string[100];
	char *str=string;
	int a[MAXSIZE]={0};
	printf("请输入要排序的数字\n");
	gets(string);
	while(*str!='\0')
	{
		while(*str!=' '&&*str!='\0')
		{
			a[len]=a[len]*10+*str-'0';
			str++;
		}
		len++;
		while(*str==' ')
		str++;
	}
	print(a,len);
	Quick_sort(a,len);
	print(a,len);
	return 0;
	
}

运行结果：