VC库中快排函数的详解

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,因为在排序过程中会涉及到一个元素交换多次的情况。

手工实现快排请参考我的另一篇文章:经典排序之快速排序

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏令仔很忙

深入理解HashMap(及hash函数的真正巧妙之处)

原文地址:http://www.iteye.com/topic/539465 Hashmap是一种非常常用的、应用广泛的数据类型,最近研究到相关的内容,就...

31610
来自专栏极客慕白的成长之路

视觉直观感受 7 种常用的排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

9040
来自专栏Python

迭代器和生成器

一 迭代和可迭代协议 什么叫迭代 1234不可以for循环,是因为它不可迭代。那么如果“可迭代”,就应该可以被for循环了。 这个我们知道呀,字符串、列表、元组...

229100
来自专栏nummy

python抽象基类abc

python中并没有提供抽象类与抽象方法,但是提供了内置模块abc(abstract base class)来模拟实现抽象类。

15610
来自专栏我的技术专栏

图说C++对象模型:对象内存布局详解

40430
来自专栏java一日一条

Java有值类型吗?

有人看了我之前的文章『Swift 语言的设计错误』,问我:“你说 Java 只有引用类型(reference type),但是根据 Java 的官方文档,Jav...

13920
来自专栏猿人谷

快速排序

今天介绍快速排序,这也是在实际中最常用的一种排序算法,速度快,效率高。就像名字一样,快速排序是最优秀的一种排序算法。 思想 快速排序采用的思想是分治思想。 快速...

218100
来自专栏算法channel

Python:lambda表达式的两种应用场景

python书写简单,功能强大, 迅速发展成为 AI ,深度学习的主要语言。介绍Python中的lambda表达式,注意到,它只是一个表达式,不是语句啊。

14210
来自专栏落影的专栏

程序员进阶之算法练习(三十四)LeetCode专场

LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 1、2、3题都是Medium的难度,大概是头条的面试题水准; 4、5题是Hard...

13730
来自专栏阿凯的Excel

Python读书笔记19(函数与返回值)

为什么计算机与程序可以简化我们的工作量,因为我们只需要了解输入输出即可,不需要关心中间的计算过程。 那我们今天就聊一下如何使用函数输出返回值。 我们设想有一个函...

30160

扫码关注云+社区

领取腾讯云代金券