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：用于比较的第二个数据;
排序函数的返回值
| -返回值 | -对应情况 |
| = 0 | 两个数据相等 |
| > 0 | 第一个数据大于第二个数据 |
| < 0 | 第一个数据小于第二个数据 |
函数使用
我们以上面提到的 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 函数的内部也是用冒泡排序实现的，这样做明显有些得不偿失，因为冒泡排序的时间复杂度是比较高的；但是它们都能达到一样的效果，并且都是基于快速排序的思想来设计的。
