C语言快速排序实现方案（面向ACM、NOIP）

发表于 | 更新于 | | 阅读次数：

我是C++选手，但学校要求用C考试，所以来总结一下C下快速排序的实现方案。
NOIP考试时，C++下有sort，pascal下有可用的示例文件，C就比较尴尬了。
这里用手写和使用qsort的方式实现快排。

手写代码实现

快排的代码实现需要格外注意i与j的边界情况。回想以往用pascal参加NOIP的经历，保证正确性起见，遂把pascal目录下的/demo/text/qsort.pp翻译成c贴上。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
int n,a[100009];
void sort (int* a,int l,int r) {
	int i,j,x,t;
	i=l,j=r;
	x=a[(l+r)/2];
	while (i<=j) {
		while (a[i]<x) i++;
		while (x<a[j]) j--;
		if (i<=j) {
			t=a[i];
			a[i]=a[j];
			a[j]=t;
			i++;
			j--;
		}
	}
	if (l<j) sort(a,l,j);
	if (i<r) sort(a,i,r);
}
int main () {
	int i,j;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a,1,n);
	for (i=1;i<=n;i++)
		printf("%d ",a[i]);
}

顺便祭上pascal代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
procedure sort(l,r: longint);
  var
     i,j,x,y: longint;
  begin
     i:=l;
     j:=r;
     x:=a[(l+r) div 2];
     repeat
       while a[i]<x do
        inc(i);
       while x<a[j] do
        dec(j);
       if not(i>j) then
         begin
            y:=a[i];
            a[i]:=a[j];
            a[j]:=y;
            inc(i);
            j:=j-1;
         end;
     until i>j;
     if l<j then
       sort(l,j);
     if i<r then
       sort(i,r);
  end;

使用stdlib.h的qsort函数

其实在实际测试（gcc 4.7.2）中发现不引用stdlib.h也可以使用qsort。
相比于C++的algorithm中的sort函数，qsort使用起来要麻烦一些，但速度相对会快那么一点。
在stdlib.h中qsort的声明为：

1
void qsort(void *base, int nelem, unsigned int width, int ( * pfCompare)( const void *, const void *));

其中void *base为需要排序的数据的起始地址
int nelem需要排序的元素的个数
unsigned int width为每个元素的大小
int ( * pfCompare)( const void *, const void *)这个是指向比较函数的指针

相比于C++中的sort，多了元素个数、元素大小和必须加上的比较函数

需要说明几点：

1、void *base通常用数组名就可以（数组名相当于数组第一个元素的地址，即a<==>&a[0]，同理a+1<==>&a[1]）
2、int ( * pfCompare)( const void *, const void *)这是个函数指针，下面会提到
3、void *是一个特殊的指针，下面会提到
4、比较函数的返回值必须是int

函数指针

先区分两个概念：函数指针与指针函数
函数指针是指向函数的指针，指针函数是返回值为指针的函数，这里只简单提一下函数指针。

类似数组名为数组第一个元素的地址，函数名为函数的地址。
函数指针指向函数地址，如

1
int (*f) (int,int);

现在定义一个函数

1
2
3
int foo (int x,int y) {
    <foo>
}

如果给f赋值f=foo，
那么foo(1,2);<==>(*f)(1,2);<==>f(1,2);

void*指针

void是一种特殊的指针，它没有类型，可以被赋值任何类型的地址。
但要注意调用这种类型时必须加强制类型转换，而且void类型不能参与指针运算（GNU中是允许的，而ANSI C不允许）
一个例子

1
2
3
4
int a;
void* p=&a;
int* x;
x=(int*)p;

比较函数

比较函数的返回值为int，和C++中的比较函数不太一样（C++中如果是用结构体的话直接重载<就可以实现排序了），这里假设需要比较的两个元素为a和b

若 a < b 则返回值应该小于0
若 a == b 则返回值应该等于0
若 a > b 则返回值应该大于0

有些类似于strcmp的返回值

理解了这些，就不难看懂qsort的调用了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int n,a[100009];
int compare (const void *a,void *b) {
	return *((int*)a)-*((int*)b);
}
int main () {
	int i,j;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&a[i]);
	qsort(a+1,n,sizeof(int),compare);
	for (i=1;i<=n;i++)
		printf("%d ",a[i]);
}

compare是一个函数地址，在qsort引用时不用加括号

qsort还可以给结构体排序，示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
int n,a[100009];
struct Data {
	int a,b;
}data[100009];
int compare (const void *a,const void *b) {
	struct Data *x=(struct Data*)a,*y=(struct Data*)b;
	return (*x).a-(*y).a;
}
int main () {
	int i,j;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&data[i].a);
	for (i=1;i<=n;i++)
		scanf("%d",&data[i].b);
	qsort(data+1,n,sizeof(struct Data),compare);
	for (i=1;i<=n;i++)
		printf("%d ",data[i].a);
	printf("\n");
	for (i=1;i<=n;i++)
		printf("%d ",data[i].b);
}