qsort 函数

函数功能

qsort 是C语言中基于快速排序思想的一种排序函数,与我们之前学过的冒泡排序不同,qsort 可以排序任意类型的数据（整形、浮点型、数组、结构体等等）,同时,qsort 函数也是函数指针中回调函数应用的一个经典案例 .

函数参数

void qsort( void *base,
           size_t num, 
           size_t width, 
           int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

# void* base：要排序数据的起始地址,把指针类型定义为void*,让qsort函数可以接收任何类型数据的地址;
# size_t num：要排序的元素个数;
# size_t width：每个元素的大小;
# __cdecl：函数调用约定;
# int (*compare)(const void *elem1, const void *elem2 ))：函数指针,指向用于排序的函数

函数指针

假设我这里有一个名为 struct Stu 的结构体,里面有 name、age、height 三个成员变量,现在我们要调用 qsort 函数对多个这样的结构体变量进行排序,那么这里就会出现一个问题;

struct Stu 内部的排序依据有三个,分别是 name、age 和 height,我们即函数的调用者肯定是清楚我们想要以哪种依据来排序的,但是qsort 函数的实现者显然并不知道;

所以 qsort 函数中第四个参数是一个函数指针,该函数指针指向一个排序函数,该函数需要由 qsort 的调用者来提供,用于指定两个数据以何种方式进行比较.

int (*compare)(const void *elem1, const void *elem2 ));
# const void *elem1：用于比较的第一个数据;
# const void *elem2：用于比较的第二个数据;

排序函数的返回值

函数使用

我们以上面提到的 struct Stu 结构体进行举例;

以 name 为依据进行排序：

#include <stdio.h>
#include <stdlib.h> //qsort 对应头文件
#include <string.h> //strcmp 对应头文件

struct Stu
{
    
	char name[20];
	int age;
	int height;
};

int sort_by_name(const void* e1, const void* e2)  //排序函数
{
    
	//由于e1 e2 是void*类型,不能直接解引用,所以我们需要先将其强转为 struct Stu* 类型,然后再找出其中的 name 进行比较
	//由于strcmp函数和排序函数的返回值相同,且name是字符串,所以这里我们直接调用strcmp函数
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

int main()
{
    
	struct Stu stu[3] = {
     {
    "zhangsan", 23, 185}, {
    "lisi", 20, 180}, {
    "wangwu", 25, 186} };
	qsort(stu, 3, sizeof(struct Stu), sort_by_name);
	int i = 0;
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	return 0;
}

以 age 为依据进行比较：

#include <stdio.h>
#include <stdlib.h> //qsort 对应头文件

struct Stu
{
    
	char name[20];
	int age;
	int height;
};

int sort_by_age(const void* e1, const void* e2)  //排序函数
{
    
    //由于e1 e2 是void*类型,不能直接解引用,所以我们需要先将其强转为 struct Stu* 类型,然后再找出其中的 age 进行比较
	//根据排序函数的返回值要求,我们直接返回二者的差值即可
	return (((struct Stu*)e1)->age - ((struct Stu*)e2)->age);
}

int main()
{
    
	struct Stu stu[3] = {
     {
    "zhangsan", 23, 185}, {
    "lisi", 20, 180}, {
    "wangwu", 25, 186} };
	qsort(stu, 3, sizeof(struct Stu), sort_by_age);
	int i = 0;
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	return 0;
}

以 height 为依据进行比较：

#include <stdio.h>
#include <stdlib.h> //qsort 对应头文件

struct Stu
{
    
	char name[20];
	int age;
	int height;
};

int sort_by_height(const void* e1, const void* e2)  //排序函数
{
    
    //由于e1 e2 是void*类型,不能直接解引用,所以我们需要先将其强转为 struct Stu* 类型,然后再找出其中的height进行比较
	//根据排序函数的返回值要求,我们直接返回二者的差值即可
	return (((struct Stu*)e1)->height - ((struct Stu*)e2)->height);
}

int main()
{
    
	struct Stu stu[3] = {
     {
    "zhangsan", 23, 185}, {
    "lisi", 20, 180}, {
    "wangwu", 25, 186} };
	qsort(stu, 3, sizeof(struct Stu), sort_by_height);
	int i = 0;
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	return 0;
}

qsort 函数的模拟实现

我们之前学习了冒泡排序,我们知道,冒泡排序只能排序整形的数据;今天我们就用快速排序的思想来对冒泡排序进行改造,让它能够达到和 qsort 函数同样的效果,可以排序任意类型的数据.

冒泡排序

首先我们先来写一个普通的冒泡排序：

void bubble_sort(int arr[], int n)
{
    
	int i = 0;
	int j = 0;
	for (i = 0; i < n - 1; i++)
	{
    
		for (j = 0; j < n - i - 1; j++)
		{
    
			if (arr[j] > arr[j + 1])
			{
    
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

int main()
{
    
	int arr[] = {
     1,2,4,5,8,3,6,7,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);  //冒泡排序
	int i = 0;
	for (i = 0; i < sz; i++)
	{
    
		printf("%d ", arr[i]);
	}
	return 0;
}

现在我们来对冒泡排序进行改造：

首先是参数的设置,为了达到和 qsort 函数同样的效果,我们这里参数和 qsort 设置为一样;然后是代具体实现,冒泡排序的整体框架我们不用改变,要改变的地方只是元素进行比较和交换的方法.

void Swap(char* buf1, char* buf2, size_t width)
{
    
	int i = 0;
	for (i = 0; i < width; i++)  //将两个元素每一对字节的内容进行交换
	{
    
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

void bubble_sort(void* base, size_t num, size_t width, int (*cmp)(const void* e1, const void* e2))
{
    
	int i = 0;
	int j = 0;
	for (i = 0; i < num - 1; i++)
	{
    
		for (j = 0; j < num - i - 1; j++)
		{
    
			//由于base是void*的,所以不能直接对其进行+-整数的操作
			//同时又为了能够操作任意类型的数据,我们把base强转为最小数据类型的大小：char*
			//回调函数：使用排序函数的返回值判断是否要进行元素的交换
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
    
				//如果前一个元素>后一个元素,就将两个元素的数据进行交换
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}

现在我们用改造后的冒泡排序来对我们上面的结构体进行排序,检验代码的正确性：

struct Stu
{
    
	char name[20];
	int age;
	int height;
};

int sort_by_name(const void* e1, const void* e2)  //排序函数：按姓名
{
    
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

int sort_by_age(const void* e1, const void* e2)  //排序函数：按年龄
{
    
	return (((struct Stu*)e1)->age - ((struct Stu*)e2)->age);
}

int sort_by_height(const void* e1, const void* e2)  //排序函数：按身高
{
    
	return (((struct Stu*)e1)->height - ((struct Stu*)e2)->height);
}

int main()
{
    
	struct Stu stu[3] = {
     {
    "zhangsan", 23, 185}, {
    "lisi", 20, 180}, {
    "wangwu", 25, 186} };
	int i = 0;
	bubble_sort(stu, 3, sizeof(struct Stu), sort_by_name);
	printf("以姓名排序：\n");
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	printf("----------------------\n");

	bubble_sort(stu, 3, sizeof(struct Stu), sort_by_age);
	printf("以年龄排序：\n");
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	printf("----------------------\n");

	bubble_sort(stu, 3, sizeof(struct Stu), sort_by_height);
	printf("以体重排序：\n");
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	return 0;
}

我们上面只是用冒泡排序来模拟实现了 qsort 函数的功能,并不是说 qsort 函数的内部也是用冒泡排序实现的,这样做明显有些得不偿失,因为冒泡排序的时间复杂度是比较高的;但是它们都能达到一样的效果,并且都是基于快速排序的思想来设计的.