8.3冒泡排序思想实现qsort
使用冒泡排序的思想来实现一个类似于qsort这个功能的冒泡排序函数bubble_sort()
各参数组成:
base，num，width，cmp函数，elem1和elem2
接下来说明一下qsort各参数的设计思路:
①为什么base定义为void*类型?
void*是 C 语言中的一种通用指针类型，可以指向任意类型的数据。在 qsort 函数中，由于需要对不同类型的数据进行排序，因此需要使用void*类型的指针，以便能够接受各种类型的数据，base参数是一个指向要排序数组第一个元素的指针。由于它要指向任意类型的数据,所以使用void*是最通用的。
举例:
int a = 10; void* p = &a;
优点:
无具体类型的指针，所以它可以接收任何类型的地址
缺点:
*p //--> void*的指针不能解引用操作符 p++ //--> 因为不知道是什么数据类型，不能直接++
正确用法:
*(int*)p;//也可以转化成其它类型
②为什么num要设计成size_t？
- size_t 在 C 语言中是一种无符号整数类型,用于表示大小、长度和索引值,使用它表示数组元素个数很合适。
- 数组元素个数是一个非负的值,使用无符号类型size_t可以避免出现负数,更加合理。
- 使用专门的 size_t 类型比简单的 unsigned int 更能表明这个参数的语义 - 它表示一个大小或长度,而不是一个整数。
③为什么width要设计成size_t
在qsort函数中,width参数表示每个数组元素的大小(以字节为单位)
width表示一个"大小"的概念,使用size_t类型可以更清楚地表达这个参数的语义。
width的单位是字节,size_t通常是无符号整数类型,不会有负数,所以更适合表示正的值。
width需要足够大的范围来表示任意数据类型的大小。size_t类型依赖平台,但通常是机器字大小,能满足大多数数据元素的大小需求。
在访问数组元素时,索引位置需要乘以元素大小才能获得地址偏移量。既然索引是size_t类型,那么两者相乘的结果也应该是size_t类型,以避免溢出问题。
④为什么要设计一个函数指针cmp？
qsort 本身是一个通用的排序函数,不能知道要排序的元素类型,也就无法直接比较两个元素。采用函数指针可以将比较操作的实现留给用户。
通过函数指针,用户可以自行实现针对自己数据类型的比较函数,将具体的比较逻辑封装起来。这提高了qsort的通用性和灵活性。
对于不同的数据类型,比较操作的逻辑可能不同。使用函数指针实现可以避免在qsort中写大量的条件分支逻辑。
函数指针提供了一种扩展机制。如果用户需要改变比较操作的逻辑,只需要传入一个新的函数指针就可以,而不需要改动qsort函数本身。
⑤为什么elem1和elem2类型是const void*类型?
qsort要对任意类型的数据进行排序,所以比较函数需要能处理任意类型的元素。使用void*可以指向任意类型的数据,const用于表示不应修改指针指向的内容。
qsort要对任意类型的数据进行排序,所以比较函数需要能处理任意类型的元素。使用void*可以指向任意类型的数据,const用于表示不应修改指针指向的内容。
在调用qsort时可以直接将数组元素的地址强制转换为const void* 类型传给比较函数,简化调用。
qsort函数本身不需要了解元素具体类型,只要把void*指针传给比较函数,由比较函数转换并解释指针内容即可。
开始模拟实现:冒泡排序大题思路不需要改变，只需要对排序方式进行即可
int cmp_int(const void* p1, const void* p2) { return *(int*)p1 - *(int*)p2; } //假设排序为升序 //希望这个bubble_sort函数可以排序任意类型的数据 void Swap(char* buf1, char* buf2, int width) { int i = 0; for (i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } } //假设排序为升序 //希望这个bubble_sort函数可以排序任意类型的数据 void bubble_sort(void* base, size_t num, size_t width, int (*cmp)(const void* p1, const void* p2)) { //冒泡排序大题思路不需要改变，只需要对排序方式进行即可 //要确定趟数 size_t i = 0; for (i = 0; i < num - 1; i++) { int flag = 0;//假设已经有序了 //一趟冒泡排序的过程 size_t j = 0; for (j = 0; j < num - 1 - i; j++) { //两个相邻的元素比较 //arr[j] arr[j+1] if (cmp((char*)base + j * width, (char*)base+(j+1)*width)>0) { //交换 flag = 0; Swap((char*)base+j*width,(char*)base+(j+1)*width,width); } } } } void print_arr(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } void test3() { int arr[] = { 3,1,5,2,4,9,8,6,5,7 }; int sz = sizeof(arr) / sizeof(arr[0]); printf("排序前:"); print_arr(arr, sz); bubble_sort(arr, sz, sizeof(arr[0]), cmp_int); printf("排序后:"); print_arr(arr, sz); }
qsort对于代码的解析:
如何交换数据：
为什么这个地方写成char*？
在bubble_sort函数中，由于不知道base指向的数据类型，因此需要将其强制转换为char*类型，从而让指针的步长为1。这样，在进行指针的加减运算时，就可以根据width参数来控制指针的步长，从而实现对任意数据类型的排序。
注意:width对于char来说是1个字节的意思，但是对于其它类型来说就不是了，width是根据参数不同来设置不同的数据类型，控制指针步长的。
交换的流程:1,2,3,4表示顺序
代码的整体流程:
排序:
通过新定义的冒泡排序排序年龄以及姓名
struct Stu { char name[20]; int age; }; int cmp_stu_by_age(const void*p1,const void* p2) { return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age; } int cmp_stu_by_name(const void* p1, const void* p2) { return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name); } void Swap(char* buf1, char* buf2, int width) { int i = 0; for (i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } } //假设排序为升序 //希望这个bubble_sort函数可以排序任意类型的数据 void bubble_sort(void* base, size_t num, size_t width, int (*cmp)(const void* p1, const void* p2)) { //要确定趟数 size_t i = 0; for (i = 0; i < num - 1; i++) { int flag = 0;//假设已经有序了 //一趟冒泡排序的过程 size_t j = 0; for (j = 0; j < num - 1 - i; j++) { //两个相邻的元素比较 //arr[j] arr[j+1] if (cmp((char*)base + j * width, (char*)base+(j+1)*width)>0) { //交换 flag = 0; Swap((char*)base+j*width,(char*)base+(j+1)*width,width); } } } } void print_arr3(struct Stu* s, int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", (s + i)->age); //printf("%s ", (*(arr+i)).name); //printf("%s ", arr[i].name); } printf("\n"); } void print_arr4(struct Stu* s, int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%s ", (s+i)->name); //printf("%s ", (*(arr+i)).name); //printf("%s ", arr[i].name); } printf("\n"); } void test4() { struct Stu s[] = { {"zhangsan",30} ,{"lisi",25},{"wangwu",50}}; int sz = sizeof(s) / sizeof(s[0]); //测试按年龄来排序 /*print_arr3(s, sz); bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_age); print_arr3(s, sz);*/ //测试按照名字来排序 print_arr4(s, sz); bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_name); print_arr4(s, sz); }
按姓名排序：
按年龄排序
这篇文章到这里就结束了，如有错误欢迎大家指正，然后下来就是这篇关于sizeof和strlen的详细总结:,指针和数组笔试题解析总结,传送门--> http://t.csdn.cn/aKVsj
欢迎大家来访。
