模拟实现通用型排序
本期介绍🍖
主要介绍：什么是泛型排序，即：无类型排序，以及库函数qsort()的使用，以及如何自己模拟实现一个泛型的冒泡排序。
文章目录
- 1. 什么是通用型排序
- 2. 库函数qsort()
- 2.1 定义
- 2.2 使用
- 3. 模拟实现通用类型的冒泡排序
1. 什么是通用型排序
之前我们实现过冒泡排序，如下所示。但该排序只能对int型数组进行排序，因为在编写这个函数的时候，就是以排序整型来实现的。如若想排序其他类型的数据，只能重新实现排序函数。那有没有什么办法，让一个排序函数能够排序所有类型的数据呢？有的，那就是：通用类型排序。
//冒泡排序
void bubble_sort(int arr[], int num)
{
//趟数
int i = 0;
for (i = 0; i < num - 1; i++)
{
//每趟两两交换次数
int j = 0;
for (j = 0; j < num - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
2. 库函数qsort()
2.1 定义
在C语言的库中就存在着一个函数qsort()快速排序，该排序就是上述的通用类型排序，使用前需要引用头文件stdlib.h。函数声明定义如下：
void qsort (void* base, size_t num, size_t size,
int(*cmp)(const void* p1, const void* p2));
qsort()函数的返回类型为void，表示没有返回值，函数有4个参数，如下所示：
- base：是
void*类型的指针，该指针指向待排序数组的起始位置。
- num：是待排序数组中元素的个数
- size：是待排序数组中每个元素的大小（单位：字节）
- cmp：是函数指针，指针的类型为
int(*)(const void* p1, const void* p2))，该指针指向的函数返回类型为int，函数有两个参数p1和p2，都为泛型指针且类型都是const void*。该函数会被qsort()调用，用于比较两个元素的大小，并返回值，返回值的规则如下所示。
如果p1指向的元素>p2指向的元素，那么返回一个大于0的数。如果p1指向的元素<p2指向的元素，那么返回一个小于0的数。如果p1指向的元素=p2指向的元素，那么返回值为0。
2.2 使用
首先需要了解，qsort()函数的参数cmp指向的那个比较函数，是需要qsort()函数的调用方自己实现的。因为不同类型数据的比较方式是完全不一样的，就比如char、int、float、double可以使用>、<、=操作符比较大小，但字符串就不行，结构体也不行。所以只能是qsort()函数的调用方自己实现，然后将实现的比较函数的地址作为参数传给qsort()函数，qsort()函数在某个时机返回来调用比较函数，这就是回调函数的用法。qsort()函数实际使用如下：
- 排序整型数组
#include<stdio.h>
#include<stdlib.h>
void print(int* parr, size_t num)
{
int i = 0;
for (i = 0; i < num; i++)
{
printf("%d ", parr[i]);
}
printf("\n");
}
int cmp_int(const void* p1, const void* p2)
{
return *(int*)p1 - *(int*)p2;
}
int main()
{
int arr[] = { 3,1,4,5,7,2,9,8,0,6 };
size_t num = sizeof(arr) / sizeof(arr[0]);
size_t size = sizeof(arr[0]);
qsort(arr, num, size, cmp_int);
print(arr, num);
return 0;
}
- 排序字符串
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void print(char* arr[], size_t num)
{
int i = 0;
for (i = 0; i < num; i++)
{
printf("%s\n", arr[i]);
}
}
int cmp_str(const void* p1, const void* p2)
{
return strcmp(*(char**)p1, *(char**)p2);
}
int main()
{
char* arr[] = { "zhangsan", "lisi", "wangwu"};
size_t num = sizeof(arr) / sizeof(arr[0]);
size_t size = sizeof(arr[0]);
qsort(arr, num, size, cmp_str);
print(arr, num);
return 0;
}
- 排序结构体数组
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct stu
{
char name[20];
int age;
}stu;
void print(stu* parr, size_t num)
{
int i = 0;
for (i = 0; i < num; i++)
{
printf("%s %d\n", parr[i].name, parr[i].age);
}
printf("\n");
}
int cmp_stu_age(const void* p1, const void* p2)
{
return ((stu*)p1)->age - ((stu*)p2)->age;
}
int main()
{
stu arr[] = { {"zhangsan", 25},{"lisi", 38},{"wangwu", 17} };
size_t num = sizeof(arr) / sizeof(arr[0]);
size_t size = sizeof(arr[0]);
qsort(arr, num, size, cmp_stu_age);
print(arr, num);
return 0;
}
3. 模拟实现通用类型的冒泡排序
根据qsort()函数，模拟实现一个通用类型的冒泡排序。由于无法得知需要排序数组的类型，冒泡排序函数接受待排序数组的地址的类型就不确定，故只能通过泛型指针void*来接收。
值得注意，void*类型的指针是无具体类型的，能够存放所有类型的地址，但无法对其进行解引用*和加减整数+、-操作。因为无法确定其指向元素的类型，所有对其进行解引用该访问多大空间不确定，加减整数操作步长是多大也不确定。冒泡函数的声明如下：
void bubble_sort (void* base, size_t num, size_t size,
int(*cmp)(const void* p1, const void* p2));
问：为什么通用类型排序需要知道待排序数据元素的大小呢？带着这个问题接着往下看。
通用类型的冒泡函数与原冒泡函数相比，排序的算法思路是不变的，依然是相邻两个元素进行两两比较，一共要进行n-1趟。故冒泡排序代码的算法框架是不需要改变的。如下所示：
void bubble_sort (void* base, size_t num, size_t size,
int(*cmp)(const void* p1, const void* p2))
{
//趟数
int i = 0;
for (i = 0; i < num - 1; i++)
{
//每趟两两交换次数
int j = 0;
for (j = 0; j < num - 1 - i; j++)
{
if ()//比较两个元素的大小
{
//交换两个元素
}
}
}
}
当执行到if(……)，该如何实现比较两个元素的大小？由于待比较的两个元素的类型不确定，比较的方法自然也不同。所以只能是调用函数方，自己实现比较函数，并将函数的地址作为参数传递进来。但是问题来了，由于此时指向函数起始位置指针base是void*类型的，无法进行加减整数操作，那么调用函数的时候，待比较的两个元素的地址该如何获得？
如果待比较的两个元素是int型，那么加减整数一次就需要跳过1个整型4个byte。但是我们在实现排序函数时，是不知道两个元素是int型的，所以不能将base指针强制类型转化为(int*)。该怎么办呢？
解决方案：将base指针强制类型转换为(char*)类型，那么此时base指针加减1就能跳过1个byte。想要找到元素的地址，就只需要将base + (下标)*(元素的大小)即可。如下所示：
void bubble_sort(void* base, size_t num, size_t size, int cmp(const void* p1, const void* p2))
{
//趟数
int i = 0;
for (i = 0; i < num - 1; i++)
{
//每趟两两交换次数
int j = 0;
for (j = 0; j < num - 1 - i; j++)
{
if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
//……
}
}
}
}
继续往下执行，需要实现交换两个元素。但问题来了，由于不确定交换的两个元素的类型，无法通过解引用操作一次性访问整个元素来进行交换。该怎么解决？
解决方案：先将元素的地址强制类型转化为(char*)，一个字节一个字节的进行交换，一共交换size元素大小次，就能完成两个元素的交换了。将交换两个元素封装成一共函数，并将两个元素的地址和元素的大小作为参数传递给函数。如下所示：
void swap(void* s1, void* s2, size_t size)
{
int i = 0;
for (i = 0; i < size; i++)
{
char tmp = *((char*)s1 + i);
*((char*)s1 + i) = *((char*)s2 + i);
*((char*)s2 + i) = tmp;
}
}
void bubble_sort(void* base, size_t num, size_t size, int cmp(const void* p1, const void* p2))
{
//趟数
int i = 0;
for (i = 0; i < num - 1; i++)
{
//每趟两两交换次数
int j = 0;
for (j = 0; j < num - 1 - i; j++)
{
if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
}
}
}
}
下面来验证一下模拟实现的通用冒泡排序函数是否可行。
- 排序整型
#include<stdio.h>
void swap(void* s1, void* s2, size_t size)
{
int i = 0;
for (i = 0; i < size; i++)
{
char tmp = *((char*)s1 + i);
*((char*)s1 + i) = *((char*)s2 + i);
*((char*)s2 + i) = tmp;
}
}
void bubble_sort(void* base, size_t num, size_t size, int cmp(const void* p1, const void* p2))
{
//趟数
int i = 0;
for (i = 0; i < num - 1; i++)
{
//每趟两两交换次数
int j = 0;
for (j = 0; j < num - 1 - i; j++)
{
if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
}
}
}
}
int cmp_int(const void* p1, const void* p2)
{
return *(int*)p1 - *(int*)p2;
}
void print(int arr[], size_t num)
{
int i = 0;
for (i = 0; i < num; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
int num = sizeof(arr) / sizeof(arr[0]);
int size = sizeof(arr[0]);
bubble_sort(arr, num, size, cmp_int);
print(arr, num);
return 0;
}
- 排序结构体
#include<stdio.h>
#include<string.h>
typedef struct stu
{
char name[20];
int age;
}stu;
void swap(void* s1, void* s2, size_t size)
{
int i = 0;
for (i = 0; i < size; i++)
{
char tmp = *((char*)s1 + i);
*((char*)s1 + i) = *((char*)s2 + i);
*((char*)s2 + i) = tmp;
}
}
void bubble_sort(void* base, size_t num, size_t size, int cmp(const void* p1, const void* p2))
{
//趟数
int i = 0;
for (i = 0; i < num - 1; i++)
{
//每趟两两交换次数
int j = 0;
for (j = 0; j < num - 1 - i; j++)
{
if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
}
}
}
}
void print(stu arr[], size_t num)
{
int i = 0;
for (i = 0; i < num; i++)
{
printf("%s %d\n", arr[i].name, arr[i].age);
}
printf("\n");
}
int cmp_stu_name(const void* p1, const void* p2)
{
return strcmp(((stu*)p1)->name, ((stu*)p2)->name);
}
int main()
{
stu arr[] = { {"zhangsan", 25},{"lisi", 38},{"wangwu", 17} };
size_t num = sizeof(arr) / sizeof(arr[0]);
size_t size = sizeof(arr[0]);
bubble_sort(arr, num, size, cmp_stu_name);
print(arr, num);
return 0;
}
这份博客👍如果对你有帮助，给博主一个免费的点赞以示鼓励欢迎各位🔎点赞👍评论收藏⭐️，谢谢！！！
如果有什么疑问或不同的见解，欢迎评论区留言欧👀。