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 ))：函数指针，指向用于排序的函数
1
2
3
4
5
6
7
8
9
10

函数指针

假设我这里有一个名为 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：用于比较的第二个数据;
1
2
3

排序函数的返回值

函数使用

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

以 name 为依据进行排序：

#include 
#include   //qsort 对应头文件
#include   //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;
}
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

以 age 为依据进行比较：

#include 
#include   //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;
}
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

以 height 为依据进行比较：

#include 
#include   //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;
}
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

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;
}
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
30

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

首先是参数的设置，为了达到和 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);
			}
		}
	}
}
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
30
31
32

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

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;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

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

---