快速排序

（一）C语言提供了qsort库函数，它可以对各种类型的数组包括结构体数组进行排序，它的原型是void qsort(void *base,int nelem,int width,int (*cmp)(const void *,const void *)),base是待排序的数组首地址，nelem是数组中排序的元素数量，width是排序元素的大小，cmp是函数指针，用来确定排序的顺序。qsort函数位于头文件stdlib.h中。函数指针cmp,int cmp(const void *a,const void *b)中有两个形参，如果返回值大于0，就认为a>b,小于0就认为a<b,如果想降序排序，只要在函数体中让a和b的位置互换。调用qsort函数的例子为：

# include <stdlib.h>
# include <stdio.h>
# include <string.h>
int comp(const void *p1,const void *p2)
{
	return *((int *)p1)-*((int *)p2);
}
int main()
{
	int i;
	int  a[10]={1,345,677,9,4,5,7,4};
	qsort(a,sizeof(a)/sizeof(int),sizeof(int),comp);
	for (i=0;i<10;i++)
		printf("%d\n",a[i]);
	system("pause");
        return 0;
}

（二）快速排序是在实践中较快的排序算法，它的平均复杂度是O（NlogN）,最坏的情形是O（N^2）,它是一种分治的递归算法。将数组S排序的基本算法由以下四步组成，1，如果S中的元素个数是0或者1，则返回2，取S中任一元素，称之为枢纽元，3，将S-{v}分成两个不想交的集合，分别为小于等于v的数的集合S1和大于等于v的集合S2。4继续对S1和S2进行快速排序。第二步中的枢纽元的选择方法不唯一。

快速排序的示意图为：

可以看出，经过一趟排序后，比枢纽元小的元素在左边，比枢纽元大的元素在右边，这时，需要对递归和分治的方法对左边元素和右边元素进行排序。

快速排序的程序为：

# include <iostream>
using namespace std;
int main()
{  void f(int a[],int left,int right);
int i;
	int a[10]={1,34,39,69,5,43,45,9,0,10};
	f(a,0,9);
	for(i=0;i<10;i++)
		printf("%d\t",a[i]);
	cin.get();
return 0;
}

void f(int a[],int left,int right)
{
	if(left>right)
		return ;
int i=left,j=right,t;
int temp=a[left];
while(i<j){
	
for(;a[j]>=temp&&i<j;j--)
	;
if(i<j)
{
a[i++]=a[j];
}
for(;a[i]<=temp&&i<j;i++)
	;
if(i<j)
{
a[j--]=a[i];
}
}
a[i]=temp;
f(a,left,i-1);
f(a,i+1,right);
}

快速排序,布布扣,bubuko.com

快速排序

原文：http://blog.csdn.net/u011608357/article/details/20801981