排序算法三之快速排序

参考http://blog.csdn.net/morewindows/article/details/6684558

1.原理：：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

#include <stdio.h>
#define N 5
/*快速排序
1.先从数组中选一个基准数（支点）；
2.进行分区，把小于等于支点数的放在支点左边，大于支点数的放在右边；具体操作过程就是：从右开始找第一个小于支点的数，移动到左端；
从左开始找第一个大于支点的数，移动到右端；如此反复交叉运行；直到i==j，把支点值记录到正确的地方，一趟结束
3.再对左右区间进行第二步，直到个区间只有一个数；
*/
void quicksort(int a[],int left,int right) //形参left用来表示区间的头，right表示区间的表尾，
{
	if(left<right)//当区间只有1个元素时，此时left=right，递归调用就此结束
	{
		int i=left,j=right,pivot=a[left];//pivot支点位置,初始时就用第一个元素表示
		while(i<j)//当i==j时，一趟排序结束
		{
			while(i<j && a[j]>=pivot)//从右向左找第一个小于pivot的值
				j--;
			if(i<j)
				a[i++]=a[j];//找到后就填坑
			while(i<j && a[i]<pivot)//从左向右找第一个大于pivot的值
				i++;
			if(i<j)
				a[j--]=a[i];//a[j]=a[i];j--

		}
		a[i]=pivot;//最后填入支点值
		quicksort(a,left,i-1);//对左区间递归调用，此刻i=j是支点的位置
		quicksort(a,j+1,right);//对右区间递归排序
	}
	
}


/*输出结果*/
void print(int a[],int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		printf("%d",a[i]);
	}
	printf("n");
}
int main(void)
{
	int a[]={3,5,1,6,7};
	quicksort(a,0,4);
	print(a,N);
	return 0;
}

最后

以上就是漂亮酒窝为你收集整理的排序算法三之快速排序的全部内容，希望文章能够帮你解决排序算法三之快速排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。