效果图制作网站有哪些,商丘网约车都有哪些平台,哈尔滨网站定制公司,网站开发流程的三个部分C语言之qsort()函数的模拟实现 文章目录 C语言之qsort()函数的模拟实现1. 简介2. 冒泡排序3. 对冒泡排序进行改造4. 改造部分4.1 保留部分的冒泡排序4.2 比较部分4.3 交换部分 5. bubble_sort2完整代码6. 使用bubble_sort2来排序整型数组7. 使用bubble_sort2来排序结构体数组7.…C语言之qsort()函数的模拟实现 文章目录 C语言之qsort()函数的模拟实现1. 简介2. 冒泡排序3. 对冒泡排序进行改造4. 改造部分4.1 保留部分的冒泡排序4.2 比较部分4.3 交换部分 5. bubble_sort2完整代码6. 使用bubble_sort2来排序整型数组7. 使用bubble_sort2来排序结构体数组7.1 按名字来排序结构体数组7.2 按年龄来排序结构体数组 1. 简介 qsort()函数全称为Quicksort因为底层使用的是快速排序对初学者来说只学过冒泡排序使用我们使用冒泡排序来实现下qsort()函数qsort()函数冒泡排序版 不知道qsort函数怎么使用的可以看看这篇qsort函数
2. 冒泡排序
既然要使用冒泡排序改模拟实现qsort那得知道什么是冒泡排序 代码如下
#include stdio.hvoid bubble_sort(int arr[], int sz)
{int i 0;//趟数for (i 0; i sz - 1; i){//一趟冒泡排序int j 0;for (j 0; j sz - 1 - i; 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,4,7,2,5,8,3,10,6,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;
}3. 对冒泡排序进行改造
void bubble_sort(int arr[], int sz);
void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));先来看看冒泡排序和qsort函数的函数声明 要想用冒泡排序模拟实现qsort函数首先函数的形参要一致
void bubble_sort2(void* base,size_t sz,size_t width, int (*cmp)(const void* p1,const void* p2));仿照着qsort的形参来写
void*由于我们不知道要排序什么数组所以我们使用void*来接收sz为数组中元素的个数width为数组中一个元素的大小单位为字节int (cmp)(const void p1,const void* p2)是函数指针 这个函数指针指向的函数是用来比较两个元素的大小 p1指向一个元素p2也指向一个元素
函数的声明部分写好了就得改造函数内部了 先来看看冒泡排序中的代码
首先函数的形参得更改吧 改为上边的函数声明趟数取决于数组中元素个数使用不需要修改冒泡排序只能排序整型所以一趟冒泡排序中的比较部分需要修改交换两个元素的位置也需要修改
4. 改造部分
4.1 保留部分的冒泡排序
先将冒泡排序还能使用的部分保留下来
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i 0;//趟数for (i 0; i sz - 1; i){int j 0;//一趟冒泡排序for (j 0; j sz - 1 - i; j){//比较两个元素的大小if (){//Swap用于交换两个元素的位置Swap();}}}
}int main()
{int arr[] { 1,4,7,2,5,8,3,10,6,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;
}其中的比较部分和交换部分需要我们自己来实现
4.2 比较部分
cmp((char*)base j * width, (char*)base (j 1) * width)由于我们得到的数组名也就是首元素的地址不知道第二个元素的地址 我们可以通过指针偏移来找到第二个元素 我们得到的是void类型的数据我们需要将其强制转换成char类型的数据以便于我们进行指针偏移 不知道数组的类型我们只知道一个元素的大小我们可以通过(char*)base j width的方式来找到一个元素的地址(char*)base (j1) width的方式来找到后一个元素的地址 用来模拟arr[j] 和 arr[j1] 为什么其他类型的指针不行呢我来举个例子 假设用来排序double类型的数据也就是每个元素是8字节 width 8 (char*)base j * width 和 (char*)base (j1) * width 当j等于0时char类型的指针会偏移8个字节找到第二个元素 如果换成其他类型的指针 int* 在这个情况下就不能使用了只有char*类型的指针偏移是1个字节适用于任意类型的排序 4.3 交换部分
void Swap(char* p1, char* p2,size_t width)
{int i 0;for (i 0; i width; i){char tmp *p1;*p1 *p2;*p2 tmp;p1;p2;}
}由于在比较部分已经将数据强制转换成char类型所以Swap函数的形参就可以使用char来接收由于不知道接收的是什么类型的数据但是我们知道每个元素的大小我们可以通过一个字节一个字节进行交换和冒泡排序一样定义一个临时变量来交换两个元素交换完一个字节的内容之后p1 p2来找到第二个字节的内容直到交换完成
5. bubble_sort2完整代码
void Swap(char* p1, char* p2,size_t width)
{int i 0;for (i 0; i width; i){char tmp *p1;*p1 *p2;*p2 tmp;p1;p2;}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i 0;//趟数for (i 0; i sz - 1; i){int j 0;//一趟冒泡排序for (j 0; j sz - 1 - i; j){//比较两个元素的大小if (cmp((char*)base j * width, (char*)base (j 1) * width) 0){//Swap用于交换两个元素的位置Swap((char*)base j * width, (char*)base (j 1) * width,width);}}}
}6. 使用bubble_sort2来排序整型数组
和使用qsort函数一样第四个形象需要根据需要排序的数据类型来编写函数然后将其传给qsort函数整型数据的比较只需要两个元素作差就好了 代码如下
int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}排序整型数组的完整代码
#include stdio.hvoid Swap(char* p1, char* p2,size_t width)
{int i 0;for (i 0; i width; i){char tmp *p1;*p1 *p2;*p2 tmp;p1;p2;}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i 0;//趟数for (i 0; i sz - 1; i){int j 0;//一趟冒泡排序for (j 0; j sz - 1 - i; j){//比较两个元素的大小if (cmp((char*)base j * width, (char*)base (j 1) * width) 0){//Swap用于交换两个元素的位置Swap((char*)base j * width, (char*)base (j 1) * width,width);}}}
}int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}int main()
{int arr[] { 1,4,7,2,5,8,3,10,6,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;
}代码运行结果如下
7. 使用bubble_sort2来排序结构体数组
由于结构体中的数据类型较多可以选择一种来排序然后根据不同的数据类型来排序 按以下两种数据来举例子
struct Stu
{char name[20];int age;
};c
int main()
{struct Stu arr[] { {zhangsan,25},{lisi,18} ,{wangwu,30} };int sz sizeof(arr) / sizeof(arr[0]);bubble_sort2(arr, sz, sizeof(arr[0]), cmp_struct_by_name);int i 0;for (i 0; i sz; i){printf(%s %d\n, arr[i].name, arr[i].age);}return 0;
}7.1 按名字来排序结构体数组
字符串的比较是比较ASCII不是比较字符串的长度
int cmp_struct_by_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)-name, ((struct Stu*)p2)-name);//return strcmp((*(struct Stu*)p1).name, (*(struct Stu*)p2).name);//两段代码等价
}完整代码如下
#include stdio.h
#include string.hvoid Swap(char* p1, char* p2,size_t width)
{int i 0;for (i 0; i width; i){char tmp *p1;*p1 *p2;*p2 tmp;p1;p2;}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i 0;//趟数for (i 0; i sz - 1; i){int j 0;//一趟冒泡排序for (j 0; j sz - 1 - i; j){//比较两个元素的大小if (cmp((char*)base j * width, (char*)base (j 1) * width) 0){//Swap用于交换两个元素的位置Swap((char*)base j * width, (char*)base (j 1) * width,width);}}}
}struct Stu
{char name[20];int age;
};int cmp_struct_by_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)-name, ((struct Stu*)p2)-name);//return strcmp((*(struct Stu*)p1).name, (*(struct Stu*)p2).name);//两段代码等价
}int main()
{struct Stu arr[] { {zhangsan,25},{lisi,18} ,{wangwu,30} };int sz sizeof(arr) / sizeof(arr[0]);bubble_sort2(arr, sz, sizeof(arr[0]), cmp_struct_by_name);int i 0;for (i 0; i sz; i){printf(%s %d\n, arr[i].name, arr[i].age);}return 0;
}代码运行结果如下
7.2 按年龄来排序结构体数组
int cmp_struct_by_age(const void* p1, const void* p2)
{return ((struct Stu*)p1)-age - ((struct Stu*)p2)-age;//return (*(struct Stu*)p1).age - (*(struct Stu*)p2).age;//两段代码等价
}完整代码如下
#include stdio.h
void Swap(char* p1, char* p2,size_t width)
{int i 0;for (i 0; i width; i){char tmp *p1;*p1 *p2;*p2 tmp;p1;p2;}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i 0;//趟数for (i 0; i sz - 1; i){int j 0;//一趟冒泡排序for (j 0; j sz - 1 - i; j){//比较两个元素的大小if (cmp((char*)base j * width, (char*)base (j 1) * width) 0){//Swap用于交换两个元素的位置Swap((char*)base j * width, (char*)base (j 1) * width,width);}}}
}struct Stu
{char name[20];int age;
};int cmp_struct_by_age(const void* p1, const void* p2)
{return ((struct Stu*)p1)-age - ((struct Stu*)p2)-age;//return (*(struct Stu*)p1).age - (*(struct Stu*)p2).age;//两段代码等价
}
int main()
{struct Stu arr[] { {zhangsan,25},{lisi,18} ,{wangwu,30} };int sz sizeof(arr) / sizeof(arr[0]);bubble_sort2(arr, sz, sizeof(arr[0]), cmp_struct_by_age);int i 0;for (i 0; i sz; i){printf(%s %d\n, arr[i].name, arr[i].age);}return 0;
}代码运行结果如下
