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 数组排序

实例2：对double型数组排序,原理同int 

注意：由于两个double型的数据不可能相等，只能通过fabs(a-b)<1e-20之类的来判断，所以此处通过返回 1 和 - 1来判断

现在只显示比较函数，测试和上面一致。（下同）

实例3：对字符数组排序，原理同int

实例4：对结构体排序 （两个数据，一个相等在比较另一个）

实例5：对字符串数组排序（char s[][]）

实例6：对指针数组排序（char *s[]）

实例7：按指定方式排序（这个是我一直没遇到的，一个网友写的，不过和其他的大同小异）

如对只有大小写字母的字符串"AajkuKdYUBCDwyz"进行排序，要求大写字母在前，小写字母在后

下面是一个网友写的代码，个人感觉很好。

4、说明：

快排是不稳定的，这个不稳定表现在两个方面：

一方面是时间的不确定，最好情况O(n) ，最坏情况O(n^2);而我们常说的O(nlog(n))是平均时间，不过即使这样，使用快排还是既方便又快捷的。

另一方面是元素的顺序在排序前后可能会不一样，比如：2 3 4 3 我用 2 3a 4 3b 表示，排序后可能变成 2 3b 4 3a，因为在排序过程中会涉及到一个元素交换多次的情况。

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