Author: bakari Date: 2012.8.9
以前都是自己手动写这个算法,觉得也不是一件很麻烦的事,但现在写的程序基本上都用得着快排,重新去写这个算法很没有必要。直接使用VC库中提供的qsort方便了很多,并且百试不爽。今天总结一下这个函数的强大之处。
1、函数原型:
void qsort(void *base,size_t num,size_t width, int (__cdecl *compare )(const void *, const void *) );
第一个是数组地址,第二是数组大小,第三个是数组中每个元素的字节数,最后一个是个比较函数的函数指针,表示以一种什么样的方式比较数组的大小。(当然这个不一定是数组啊,可以是任意数据类型,我用数组是方便描述)
一般典型的用法是像这样(反正我是这样用):qsort(s,n,sizeof(s[0]),cmp); //这里用sizeof(s[0])有一个好处,下面会讲。
所在的头文件:#include <stdlib.h>
2、拆解参数:
先看这个比较函数:
函数原型:int cmp(const void *a,const void *b);
返回类型为 int,参数用const void * 就是快排的强大之处之一,表明可以为任何数据类型进行排序,只要进行强制类型转换即可。
第三个参数表示元素的大小 ,写sizeof([0])的好处是在遇到对结构体排序时,写成n * sizeof( int )这样会出问题,写成sizeof([0])方便保险,而且想对数组中任意其他元素进行排序时,只需稍作修改即可,如:qsort(&s[i], n, sizeof(s[i]) , cmp);
3、举例说明:
实例1:最常见的,对 int 数组排序
1 #include <stdlib.h>
2
3 int cmp(const void *a, const void *b)
4 {
5 return(*(int *)a-*(int *)b);
6 }
7
8 int main()
9 {
10 //输入
11
12 qsort(s,n,sizeof(s[0]),cmp);
13
14 //输出
15
16 return 0;
17 }
实例2:对double型数组排序,原理同int
注意:由于两个double型的数据不可能相等,只能通过fabs(a-b)<1e-20之类的来判断,所以此处通过返回 1 和 - 1来判断
现在只显示比较函数,测试和上面一致。(下同)
1 int cmp(const void * a, const void * b)
2 {
3 return((*( double* ) a - *(double*) b >0 ) ? 1 : -1);
4 }
实例3:对字符数组排序,原理同int
1 int cmp(const void *a,const void *b)
2 {
3 return(*( char * )a - *( char * )b);
4 }
实例4:对结构体排序 (两个数据,一个相等在比较另一个)
1 int cmp(const void *a,const void *b)
2 {
3 node *pA = (node *)a; //强制转换
4 node *pB = (node *)b;
5
6 if(pA->data != pB->data)
7 return ((pA->data > pB->data) ? 1 : -1); //先比较double数据
8 else
9 return strcmp(pA->str, pB->str);
10 }
实例5:对字符串数组排序(char s[][])
1 int cmp(const void *a,const void *b)
2 {
3 return(strcmp ( char* )a , ( char* )b);
4 }
实例6:对指针数组排序(char *s[])
1 char *s[100];
2
3 int cmp(const void *a,const void *b)
4 {
5 return strcmp(*( char** )a , *( char ** )b ); //注意这里,先将void型指针转为指针的指针,再取值
6 }
7
8 int main()
9 {
10 int n;
11 scanf("%d",&n);
12 for(int i = 0; i < n; i++)
13 {
14 s[i]=(char*)malloc(sizeof(char*));
15 scanf("%s",s[i]);
16 }
17
18 qsort(s,n,sizeof(s[0]),cmp);
19
20 for(int i = 0; i < n; i++) printf("%s\n",s[i]);
21
22 return 0;
23 }
实例7:按指定方式排序(这个是我一直没遇到的,一个网友写的,不过和其他的大同小异)
如对只有大小写字母的字符串"AajkuKdYUBCDwyz"进行排序,要求大写字母在前,小写字母在后
下面是一个网友写的代码,个人感觉很好。
1 int cmp(const void *a, const void *b)
2 {
3 char *pA = (char *)a;
4 char *pB = (char *)b;
5
6 bool flag1 = *pA >= 'A' && *pA <= 'Z';
7 bool flag2 = *pB >= 'A' && *pB <= 'Z';
8
9 if(pA == pB) //如果都为大写字母或都为小写字母
10 return *pA - *pB;
11 else //谁为大写字母,谁的权值小
12 return flag1 ? -1 : 1;
13 }
14
15 int main()
16 {
17 char szText[] = "AajkuKdYUBCDwyz";
18 qsort(szText,strlen(szText), sizeof(szText[0], cmp));
19 printf("%s\n",szText);
20 return 0;
21 }
4、说明:
快排是不稳定的,这个不稳定表现在两个方面:
一方面是时间的不确定,最好情况O(n) ,最坏情况O(n^2);而我们常说的O(nlog(n))是平均时间,不过即使这样,使用快排还是既方便又快捷的。
另一方面是元素的顺序在排序前后可能会不一样,比如:2 3 4 3 我用 2 3a 4 3b 表示,排序后可能变成 2 3b 4 3a,因为在排序过程中会涉及到一个元素交换多次的情况。
手工实现快排请参考我的另一篇文章:经典排序之快速排序