【万能排序之qsort、b_sort 、s_sort】

前言

我们所熟悉的冒泡排序，选择排序，插入排序，二分排序等都是基于给定的一种类型进行排序，通用性不强，但是库函数qsort可以对任意类型的数据包括字符串、结构体等进行排序，所以本章内容是了解qsort函数的使用方法和大致思想以及通过模仿qsort函数自己写出万能的排序

⭐️qsort函数

函数参数

现在我们应该清楚几点

1. qsort函数有四个参数，第一个参数是待排序数组首元素的地址，因为不清楚具体是什么类型，所以用`void*``接受
2. 第2个参数是数组的元素个数，第3个参数是数组元素的字节数
3. 第4个参数是一个指向用户自己实现的函数的指针，用户实现的函数需要告诉qsort函数一个数据怎么样才算大于另一个数据
4. 用户自己实现的函数形参是两个void*的指针，在具体比较2个数据时，用户自己知道带比较元素是什么类型的，所以需要对void*的指针进行强制类型转化

qsort函数的使用

qsort排序整形数组

void PrintArr(int* arr, int sz)
{for (int i = 0; i < sz; i++)printf("%d ", arr[i]);printf("\n");
}
//自定义比较2个整形的函数int CompareInt(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;	//需要对void*类型的指针进行强制转换为需要比较元素的类型，因为void*指针无法解引用
}
int main()
{int arr[5] = { 5, 4, 3 ,2 ,1 };qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(arr[0]), CompareInt);PrintArr(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

qsort排序结构体数组

typedef struct
{char name[10];int age;
}s;//自定义比较结构体数组元素年龄的函数
int CompareByAge(const void* e1, const void* e2)
{return ((s*)e1)->age - ((s*)e2)->age;
}
//自定义比较结构体数组元素姓名的函数
int CompareByName(const void* e1, const void* e2)
{return strcmp(((s*)e1)->name, ((s*)e2)->name);
}void PrintArrAge(s* stu, int sz)
{for (int i = 0; i < sz; i++)printf("%d ", stu[i].age);printf("\n");
}void PrintArrName(s* stu, int sz)
{for (int i = 0; i < sz; i++)printf("%s ", stu[i].name);printf("\n");
}int main()
{s stu[3] = { {"zhangsan",10 }, {"lisi",20}, {"wangwu", 30} };qsort(stu, 3, sizeof(stu[0]), CompareByAge);PrintArrAge(stu, sizeof(stu) / sizeof(stu[0]));qsort(stu, 3, sizeof(stu[0]), CompareByName);PrintArrName(stu, sizeof(stu) / sizeof(stu[0]));return 0;
}

注：在自定义排序函数时，将e1转换为结构体指针需要将e1也用括号括((s*)e1)起来因为->的优先级较高

⭐️模拟实现万冒泡排序

函数参数

模拟实现b_sort

void swap(char* buf1, char* buf2, size_t width)
{//因为不知道具体需要交换的数据的类型，所以需要传递第三个参数数据的字节数width//一个字节一个字节的交换，交换width次后，代表已经将这两个数据交换完成for (size_t i = 0; i < width; i++){int tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}
void b_sort(void* base, size_t num, size_t width, int (*compare)(const void* e1, const void* e2))
{for (size_t i = 0; i < num - 1; i++)//一趟冒泡排序{int flag = 1;	//flag为1表示数组是有序的for (size_t j = 0; j < num - 1 - i; j++){//比较数组中两个相邻的元素，因为不知道元素的类型，所以需要调用用户自定义的比较函数if (compare((char*)base + j * width, (char*)base + (j + 1) * width) > 0){flag = 0;//交换两个数，保证在前面的数比后面的数更小swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}//说明数组已经是有序的if (flag == 1)break;}
}int CompareInt(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}
int main()
{int arr[5] = { 5 , 4,  3, 2 ,1 };b_sort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(arr[0]), CompareInt);PrintArr(arr, sizeof(arr) / sizeof(arr[0]));
}

注意点

1. 想要冒泡排序可以排任何类型数据时，不需要改变冒泡排序的算法，只需要改变比较的原理，以及如何交换两个数，因为开发者在写b_sort时不知道调用者会比较哪些数据类型，所以在编写b_sort时需要将比较方法改成通用的，而这个比较方法需要知道比较数据类型的调用者自己实现
2. 在swap函数中，开发者并不知道调用者需要交换的数据类型，所以开发者需要知道调用者交换数据类型的字节数width，这样不管是什么类型，只要将需要交换的两个数据每一个字节数都交换，交换width次，最后的是两个数一定已经交换了
   
3. 在b_sort函数中的compare函数，因为我不知道需要比较的数据的类型，所以不能够知道需要跳过多少字节才到下一个数组元素，因此需要调用这传递参数width来告诉开发者比较下一个元素时要跳过width个字节数，+width跳过width个字节数的前提就是e1，e2必须强转为char*类型指针
   

⭐️模拟实现万能选择排序

函数参数

模拟实现s_sort

代码

void swap(char* buf1, char* buf2, size_t width)
{//因为不知道具体需要交换的数据的类型，所以需要传递第三个参数数据的字节数width//一个字节一个字节的交换，交换width次后，代表已经将这两个数据交换完成for (size_t i = 0; i < width; i++){int tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}
void s_sort(void* base, size_t num, size_t width, int (*compare)(const void* e1, const void* e2))
{//循环n-1次for (size_t i = 0; i < num - 1; i++){//min指向base[i]char* min = (char*)base + i * width;for (size_t j = i + 1; j < num; j++){//min > arr[j]if (compare(min, (char*)base + j * width) > 0){min = (char*)base + j * width;}}if (min != (char*)base + i * width)swap((char*)base + i * width, min, width);}
}

提醒
选择函数的实现也是主要算法没有改变，但是除了比较数据的方法和交换数据的方法改变了，还有min定义为char*类型指针，这样方便后续min直接参加算术运算

最后

个人认为弄清qsort函数的使用原理是很重要的，这种思想我认为值得参考，有兴趣的话可以将其他的排序算法也改写成万能排序

😄如果这期内容对你有帮助，希望你能够给一个免费的三连⭐️⭐️⭐️😄