|
??前面的话??
大家好！对于排序有许多中方法，比如冒泡排序，选择排序，希尔排序，插入排序，堆排序等等，但是怎样能够使用一个函数能够对多个数据类型进行排序呢？无所不知的C语言开发者提供了一个qsort函数，它能够对多种数据类型进行排序，实现各种数据类型的快速排序，这篇文章介绍qsort函数的使用及其模拟qsort函数的实现（基于冒泡排序）。
📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏??留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2021年9月7日🌴
??坚持和努力一定能换来诗与远方！
💭参考书籍：📚《明解C语言》📚《C primer plus》
💬参考在线编程网站：🌐牛客网🌐力扣
🙏作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！
博主的码云gitee，平常博主写的程序代码都在里面。
??qsort库函数
🍒函数声明
void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );
🍒库
<stdlib.h>
🍒函数功能
实现多个数据类型的快速排序。
🍒qosort函数各参数介绍
🍒compare函数
在qsort函数中，其中一个参数是函数指针，指向一个用来比较两个元素大小的函数，不妨记该函数的第一个参数为e1，第二个参数为e2，两个参数均为只可读无类型指针，该函数返回值类型为int，记为x：
实现整型类型比较的compare函数：
如果qsort需要实现实现升序：
int compare(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
那需要实现降序呢？
其实很简单，将上面return (*(int*)a - *(int*)b);改为return (*(int*)b - *(int*)a);就可以了。
实现浮点数比较的compare函数：
int compare_dou(const void* a, const void* b)
{
double com = (*(double*)a - *(double*)b);
if (com > 0)
return 1;
else if (com < 0)
return -1;
else
return 0;
}
int compare_fla(const void* a, const void* b)
{
float com = (*(float*)a - *(float*)b);
if (com > 0)
return 1;
else if (com < 0)
return -1;
else
return 0;
}
实现字符类型和字符串比较的compare函数：
int compare(const void* a, const void* b)
{
return (*(char*)a - *(char*)b);
}
实现结构体类型比较compare函数：
struct stu
{
char name[20];
int age;
double score;
};
int compare_stu(const void* a, const void* b)
{
return strcmp(((struct stu*)a)->name, ((struct stu*)b)->name);
}
🍒测试
测试主函数
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main ()
{
}
测试1：整数排序
void test1()
{
int arr[] = { 2,8,6,12,3,86,1,42,66,22,98,88 };
sz_t number = sizeof(arr) / sizeof(arr[0]);
sz_t size = sizeof(int);
sz_t i = 0;
printf("数组排序前：\n");
for (i = 0; i < number; i++)
{
printf("%d ", arr[i]);
}
qsort(arr, number, size, compare);
printf("\n数组排序后：\n");
for (i = 0; i < number; i++)
{
printf("%d ", arr[i]);
}
}
数组排序前：
2 8 6 12 3 86 1 42 66 22 98 88
数组排序后：
1 2 3 6 8 12 22 42 66 86 88 98
D:\gtee\C-learning-code-and-project\练习使用qsort\Debug\练习使用qsort.exe (进程 37064)已退出，代码为 0。
按任意键关闭此窗口. . .
测试2：双精度浮点数排序
void test2()
{
double arr[5] = { 3.5,8.9,9.2,4.8,2.1 };
sz_t number = sizeof(arr) / sizeof(arr[0]);
sz_t size = sizeof(double);
sz_t i = 0;
printf("数组排序前：\n");
for (i = 0; i < number; i++)
{
printf("%.2lf ", arr[i]);
}
qsort(arr, number, size, compare_dou);
printf("\n数组排序后：\n");
for (i = 0; i < number; i++)
{
printf("%.2lf ", arr[i]);
}
}
数组排序前：
3.50 8.90 9.20 4.80 2.10
数组排序后：
2.10 3.50 4.80 8.90 9.20
D:\gtee\C-learning-code-and-project\练习使用qsort\Debug\练习使用qsort.exe (进程 9984)已退出，代码为 0。
按任意键关闭此窗口. . .
测试3：结构体中字符串排序测试
void test3()
{
struct stu arr[3] = { {"zhangsan", 15}, {"lisi", 30},{"wangwu", 10} };
sz_t number = sizeof(arr) / sizeof(arr[0]);
sz_t size = sizeof(arr[0]);
sz_t i = 0;
printf("数组排序前：\n");
for (i = 0; i < number; i++)
{
printf("%s ", arr[i].name);
}
qsort(arr, number, size, compare_stu);
printf("\n数组排序后：\n");
for (i = 0; i < number; i++)
{
printf("%s ", arr[i].name);
}
}
数组排序前：
zhangsan lisi wangwu
数组排序后：
lisi wangwu zhangsan
D:\gtee\C-learning-code-and-project\练习使用qsort\Debug\练习使用qsort.exe (进程 29572)已退出，代码为 0。
按任意键关闭此窗口. . .
??模拟实现qsort函数
经过对qsort函数的了解，我们发现该函数能够对多种数据类型进行排序取决于传入的函数指针参数。我们以冒泡排序为例，模拟实现qsort函数。
🍋冒泡排序改装思路
先来看看冒泡排序函数
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void bubble_sort(int* arr, int size)
{
int i = 0;
for (i = 0; i < size - 1; i++)
{
int j = 0;
int flag = 1;
for (j = 0; j < size - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = 0;
}
}
if (flag)
break;
}
}
如果需要对多种数据类型进行排序，对应上面的这个冒泡排序，它所接受的参数肯定是必须改的，因为要接受多种数据类型的指针，所以传入的指针必须是无具体类型void。函数内部中循环排序的次数是没有发生改变的，所以函数内部的两层循环是不用发生改变的，但是由于传进来的是void型指针，无法进行运算和解引用，所以判断语句是需要进行改动的。
🍋冒泡排序模拟实现qsort函数
对与if语句中所对应条件，我们可以调用compare函数，将数组的前一个元素与后一个元素比较，如果该函数返回值大于0，表示数组前面的元素比后面的元素大，如果进行升序排列，我们需要对这两个元素进行交换。这个交换我们不妨封装在一个swap函数里，由于不知道数据类型，所以swap函数的参数为两个元素的无类型地址，交换的时候我们不妨强制转换为char*类型，因为char类型大小为1字节，根据需要交换元素的大小，我们一个一个地将每个单位字节的二进制序列交换，这样就完成了交换。对于如何得到相邻元素的首地址，同理我们先可以将传入指针强制转换为char*类型任何根据元素内存大小，计算的出每个元素的地址。比如数组元素内存大小为width，则相邻两元素地址可以表示为(char*)val + j * width, (char*)val + (j + 1) * width。
知道了冒泡排序哪个地方需要改装，我们来试着动手实践一下。
typedef unsigned int sz_t;
void bubble_qsort(void* val, sz_t size, sz_t width, int (*cmp)(const void* p1, const void* p2))
{
sz_t i = 0;
for (i = 0; i < size - 1; i++)
{
sz_t j = 0;
sz_t flag = 1;
for (j = 0; j < size - 1 - i; j++)
{
if (cmp((char*)val + j * width, (char*)val + (j + 1) * width) > 0)
{
swap((char*)val + j * width, (char*)val + (j + 1) * width, width);
flag = 0;
}
}
if (flag)
break;
}
}
void swap(char* buf1, char* buf2, sz_t width)
{
sz_t i = 0;
for (i = 0; i < width; i++)
{
char tmp = *(buf1 + i);
*(buf1 + i) = *(buf2 + i);
*(buf2 + i) = tmp;
}
}
这样，冒泡排序就能排序多种数据类型，模拟实现了qsort函数，当然也可以使用其他的排序方法模拟实现qsort函数。
🍋测试
测试主函数
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main ()
{
}
测试1：整数排序
void test1()
{
int arr[] = { 2,8,6,12,3,86,1,42,66,22,98,88 };
sz_t number = sizeof(arr) / sizeof(arr[0]);
sz_t size = sizeof(int);
sz_t i = 0;
printf("数组排序前：\n");
for (i = 0; i < number; i++)
{
printf("%d ", arr[i]);
}
bubble_qsort(arr, number, size, compare);
printf("\n数组排序后：\n");
for (i = 0; i < number; i++)
{
printf("%d ", arr[i]);
}
}
数组排序前：
2 8 6 12 3 86 1 42 66 22 98 88
数组排序后：
1 2 3 6 8 12 22 42 66 86 88 98
D:\gtee\C-learning-code-and-project\练习使用qsort\Debug\练习使用qsort.exe (进程 10620)已退出，代码为 0。
按任意键关闭此窗口. . .
测试2：双精度浮点数排序
void test2()
{
double arr[5] = { 3.5,8.9,9.2,4.8,2.1 };
sz_t number = sizeof(arr) / sizeof(arr[0]);
sz_t size = sizeof(double);
sz_t i = 0;
printf("数组排序前：\n");
for (i = 0; i < number; i++)
{
printf("%.2lf ", arr[i]);
}
bubble_qsort(arr, number, size, compare_dou);
printf("\n数组排序后：\n");
for (i = 0; i < number; i++)
{
printf("%.2lf ", arr[i]);
}
}
数组排序前：
3.50 8.90 9.20 4.80 2.10
数组排序后：
2.10 3.50 4.80 8.90 9.20
D:\gtee\C-learning-code-and-project\练习使用qsort\Debug\练习使用qsort.exe (进程 34200)已退出，代码为 0。
按任意键关闭此窗口. . .
测试3：结构体中字符串排序测试
void test3()
{
struct stu arr[3] = { {"zhangsan", 15}, {"lisi", 30},{"wangwu", 10} };
sz_t number = sizeof(arr) / sizeof(arr[0]);
sz_t size = sizeof(arr[0]);
sz_t i = 0;
printf("数组排序前：\n");
for (i = 0; i < number; i++)
{
printf("%s ", arr[i].name);
}
bubble_qsort(arr, number, size, compare_stu);
printf("\n数组排序后：\n");
for (i = 0; i < number; i++)
{
printf("%s ", arr[i].name);
}
}
数组排序前：
zhangsan lisi wangwu
数组排序后：
lisi wangwu zhangsan
D:\gtee\C-learning-code-and-project\练习使用qsort\Debug\练习使用qsort.exe (进程 13512)已退出，代码为 0。
按任意键关闭此窗口. .
关于qsort的内容就分享到这了！当然如果对快速排序感兴趣，可以自己使用其他的排序方法模拟实现qsort函数！还请大家多多支持！感谢感谢！
觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！
|