您现在的位置是：首页 >其他 >排序大师：探秘C语言中神奇的qsort库函数网站首页其他

本篇文章中会详细讲解C语言中的qsort库函数。我准备分2个方面来讲：

1. qsort如何使用。
2. 模拟实现qsort的效果。（注意：只是用冒泡排序的思想实现类似的效果，实际qsort的底层采用的是快速排序的思想。）

如何使用

先来看看qsort函数的描述：

翻译一下：qsort的使用需要包含stdlib.h头文件。qsort的形式是：

void qsort (void* base, size_t num, size_t size,
            int (*compar)(const void*,const void*));

qsort的作用是：对数组元素进行排序。

1. 该函数使用compar函数确定顺序，对由base指向的数组的num个元素进行排序，每个元素大小为size字节。
2. 该排序算法通过使用指向它们的指针调用指定的compar函数来比较元素对。
3. 该函数不返回任何值，但修改由base指向的数组的内容，重新排列其元素，如compar所定义的那样。
4. 等价元素的顺序是未定义的。

如果你第一次接触这个函数，可能会觉得云里雾里的。我们继续阅读文档：

对于参数的解释：

1. base: 指向要排序的数组中第一个对象的指针，转换为void*类型。
2. num: base所指向的数组中元素的数量。size_t是一个无符号整数类型。
3. size: 数组中每个元素的字节大小。size_t是一个无符号整数类型。
4. compar: 一个函数指针。

下面再详细讲解一下compar这个参数是干啥的。它是一个指向比较两个元素的函数的指针。这个函数会被qsort反复调用来比较两个元素。它应该遵循以下原型：

int compar (const void* p1, const void* p2);

以上函数接受两个指针作为参数（都转换为const void*）。该函数通过以稳定和可传递的方式返回元素的顺序来定义元素的顺序：

对于可以使用常规关系运算符进行比较的类型，通用的比较函数可能如下所示：

int compareMyType (const void * a, const void * b)
{
	if ( *(MyType*)a <  *(MyType*)b ) 
		return -1;
		
	if ( *(MyType*)a == *(MyType*)b ) 
		return 0;
		
	if ( *(MyType*)a >  *(MyType*)b ) 
		return 1;
}

以上是把文档中的内容翻译过来。这里我再总结一下：qsort函数是用来排序一个数组的，传的4个参数分别决定了：数组从哪开始、有几个元素、每个元素多大、如何比较。对于最后一点“如何比较”，是通过一个函数指针，以回调函数的形式实现的。这个函数指针指向一个函数，函数的参数是(const void* p1, const void* p2)，返回类型是int，返回值大于、小于、等于0，分别代表着p1指向的元素大于、小于、等于p2指向的元素。

举个例子：排序一个整型数组。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int cmp_int(const void* p1, const void* p2)
{
	assert(p1 && p2);

	return *(int*)p1 - *(int*)p2;
}

int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);

	qsort(arr, sz, sizeof(arr[0]), cmp_int);

	for (int i = 0; i < sz; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("
");

	return 0;
}

输出结果：

大家重点关注我如何传参的，以及compar函数是如何实现的。

传参：

1. arr是数组名，表示数组首元素的地址。
2. sz是数组元素个数。
3. sizeof(arr[0])表示数组每个元素多大，当然也可以写sizeof(int)。
4. cmp_int是函数名，表示函数的地址。

cmp_int函数的实现：void*类型的指针不能直接解引用，需要强制类型转换成int*类型再解引用。解引用后就能得到2个整数，返回它们之间的差即可，因为p1指向的元素大于p2指向的元素时，返回正数；因为p1指向的元素小于p2指向的元素时，返回负数；因为p1指向的元素等于p2指向的元素时，返回0。

模拟实现

qsort底层采用的是快速排序算法。如果采用快速排序算法来模拟实现qsort的效果，有一点复杂，不适合初学者学习。这里我使用冒泡排序的算法，写一个通用的bubble_sort函数。

下面跟着我一步一步实现。先搭个架子出来：

void bubble_sort(void* base, size_t num, size_t size, int(*cmp)(const void* p1, const void* p2))
{
	assert(base);
	assert(cmp);

	for (size_t i = 0; i < num - 1; ++i)
	{
		for (size_t j = 0; j < num - 1 - i; ++j)
		{

		}
	}
}

以上代码最重要的是明白2层循环的结束条件。

对于外层循环，决定了冒泡排序的“趟数”，由于一趟冒泡排序会把1个数排到正确的位置，那么num-1趟冒泡排序就会把num-1个数排到正确的位置，剩下的那个数的位置自然也就正确了。

对于内层循环，决定了一趟冒泡排序要比较几次。仔细想一下：一共有num个数，第一趟冒泡排序需要比较num-1次，第二趟冒泡排序需要比较num-2次，第三趟冒泡排序需要比较num-3次，后面依次递减。由于i从0开始一次递增，所以内层循环的判断条件就是j<num-1-i。

冒泡排序的思想是：每次比较2个数时，如果不满足顺序，就交换。此时我们要调用cmp函数，如果返回值是正数，说明前面的数大于后面的数，假设我们要排升序，就需要交换这2个数。

那传给cmp函数的参数是什么呢？本质上，需要比较的是数组中下标为j和j+1的元素。那如何找到这2个元素呢？这就要涉及到指针的知识点。

先说“正常”的情况。假设有一个数组是int arr[10];，下标为j和j+1的元素的地址分别为：arr+j和arr+j+1，这是因为arr作为数组名，表示数组首元素地址，类型是int*，所以+j后就会跳过j个int，就是下标为j的元素，j+1同理。

再回来看cmp函数的参数。是2个const void*类型的元素，其实就是要找到数组中下标为j和j+1的元素的地址。但是在bubble_sort函数内部，只知道数组起始地址base、数组元素个数num、数组单个元素大小size，所以下标为j的元素就应该是：(char*)base + j*size。解释一下：base作为数组首元素地址，强制类型转换成char*的好处是，加多少就会跳过多少个字节。由于要跳过j个元素，其实就是要跳过j*size个字节，所以应该在(char*)base的基础上加上j*size。同理，下标为j+1的元素的地址就应该是：(char*)base + (j+1)*size。

综上所述，继续写代码：

void bubble_sort(void* base, size_t num, size_t size, int(*cmp)(const void* p1, const void* p2))
{
	assert(base);
	assert(cmp);

	for (size_t i = 0; i < num - 1; ++i)
	{
		for (size_t j = 0; j < num - 1 - i; ++j)
		{
			if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
			{
				// 交换
				swap_bit((char*)base + j * size, (char*)base + (j + 1) * size, size);
			}
		}
	}
}

那交换的逻辑是什么呢？为什么要传3个参数呢？

首先回答第2个问题。前2个参数表示要交换的元素的起始地址，但是我们不知道单个元素有多大。可能会有朋友说：把这2个地址强制类型转换成char*类型再相减，根据数组中元素是连续存放的规则，就能得到单个元素的大小了。但是这样太麻烦了，不如直接传过去。

接下来回答如何交换的问题。只需要一个一个字节交换，所以仍然需要先把指针强制类型转换成char*类型。

void swap_bit(void* p1, void* p2, size_t size)
{
	assert(p1 && p2);

	for (size_t i = 0; i < size; ++i)
	{
		char tmp = ((char*)p1)[i];
		((char*)p1)[i] = ((char*)p2)[i];
		((char*)p2)[i] = tmp;
	}
}

其实写到这，程序已经可以跑了。但是还有一点可以优化：如果某一趟冒泡排序一个数都没有交换，那么就已经有序了，不用继续排序了。

void bubble_sort(void* base, size_t num, size_t size, int(*cmp)(const void* p1, const void* p2))
{
	assert(base);
	assert(cmp);

	for (size_t i = 0; i < num - 1; ++i)
	{
		int flag = 1; // 假设已经有序了
		for (size_t j = 0; j < num - 1 - i; ++j)
		{
			if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
			{
				flag = 0;
				// 交换
				swap_bit((char*)base + j * size, (char*)base + (j + 1) * size, size);
			}
		}
		if (flag)
		{
			return;
		}
	}
}

2个字：完美！

以下是完整的实现代码和测试代码：

#include <stdio.h>
#include <assert.h>

void swap_bit(void* p1, void* p2, size_t size)
{
	assert(p1 && p2);

	for (size_t i = 0; i < size; ++i)
	{
		char tmp = ((char*)p1)[i];
		((char*)p1)[i] = ((char*)p2)[i];
		((char*)p2)[i] = tmp;
	}
}

void bubble_sort(void* base, size_t num, size_t size, int(*cmp)(const void* p1, const void* p2))
{
	assert(base);
	assert(cmp);

	for (size_t i = 0; i < num - 1; ++i)
	{
		int flag = 1; // 假设已经有序了
		for (size_t j = 0; j < num - 1 - i; ++j)
		{
			if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
			{
				flag = 0;
				// 交换
				swap_bit((char*)base + j * size, (char*)base + (j + 1) * size, size);
			}
		}
		if (flag)
		{
			return;
		}
	}
}

int cmp_int(const void* p1, const void* p2)
{
	assert(p1 && p2);

	return *(int*)p1 - *(int*)p2;
}

int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);

	bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);

	for (int i = 0; i < sz; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("
");

	return 0;
}

总结

本篇博客主要讲解了qsort函数如何使用，以及如何把bubble_sort改造的更加通用。大家重点掌握qsort的使用，模拟实现只是帮助大家理解。

感谢大家的阅读！