整型数组的排序
废话不多说，我们直接开始测试整型数组的排序
1. //test1() 2. //{ 3. // int arr[10] = { 3,1,5,2,4,7,9,6,8,0 }; 4. // int sz = sizeof(arr) / sizeof(arr[0]); 5. // //默认是升序的 6. // qsort(arr, sz, sizeof(arr[0]), cmp_int); 7. // print(arr, sz);//打印函数 8. //}
我们通过定义一个函数cmp_int，通过cmp_int返回的参数来确定排序规则，需要注意的是：cmp_int函数的参数需要以const void *p1,const void *p2的形式来定义，表示a和b的类型是未确定的，在return中进行强制类型转换为int型。*(int*)p1-*(int*)p1表示以递增顺序，若想以递减只需将p1和p2换位,实现如下
1. //int cmp_int(const void* p1, const void* p2) 2. //{ 3. // return (*(int*)p1 - *(int*)p2);//数据类型强制转换 4. //}
结构题排序
我们刚刚说了，qsort是一个万能排序，不仅可以对整型进行排序。这里博主再给大家来一个结构题排序，创建以下结构体
1. //struct Stu 2. //{ 3. // char name[20]; 4. // int age; 5. //};
按年龄排序
使用如下
1. //int cmp_stu_by_age(const void* p1, const void* p2) 2. //{ 3. // return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age; 4. //} 5. // 6. //void test2() 7. //{ 8. // struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 50},{"wangwu", 15} }; 9. // int sz = sizeof(arr) / sizeof(arr[0]); 10. // qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_age); 11. //}
按名字排序
使用如下
1. //int cmp_stu_by_name(const void* p1, const void* p2) 2. //{ 3. // return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name); 4. //名字不能直接比较，得用strcmp进行比较 5. //} 6. // 7. //void test3() 8. //{ 9. // struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 50},{"wangwu", 15} }; 10. // int sz = sizeof(arr) / sizeof(arr[0]); 11. // qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name); 12. //}
模拟实现qsort函数（冒泡排序）
qsort函数使用的是快排序，而博主模拟的qsort使用的是冒泡排序
这里博主创建一个bubble_sort函数进行模拟，创建如下
void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*))
因为是一个冒泡排序所以使用冒泡，格式如下
1. void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*)) 2. { 3. int i = 0; 4. //趟数 5. for (i = 0; i < num - 1; i++) 6. { 7. int j = 0; 8. //一趟内部比较的对数 9. for (j = 0; j < num - 1 - i; j++) 10. { 11. ？？？？？？？？ 12. } 13. } 14. 15. }
我们现在要解决的是？？？？？中需要解决的代码
而我们在定义函数bubble_sort时有一个函数指针为cmp，这个函数指针指向的就是一判断大小的函数；
函数cmp_int实现如下
1. int cmp_int(const void* p1, const void* p2) 2. { 3. return (*(int*)p1 - *(int*)p2); 4. }
注意：博主这里进行的整型比较，所以强制转换的为整型。所转换类型由相应题而变化
这里，当p1>p2时返回1，所以我们可以进行以下设计
1. //假设需要升序cmp返回>0，交换 2. if (cmp((char*)base+j*size, (char*)base+(j+1)*size)>0)//两个元素比较，需要将arr[j],arr[j+1]的地址要传给cmp 3. { 4. //交换 5. Swap((char*)base + j * size, (char*)base + (j + 1) * size, size); 6. }
至于这里博主这里为什么要将base都强制转换成char*，是因为我们设计这个函数并不是为了只排序一种数组，而是要万能排序，char*占一个字节，作为一个基础单位，后面根据具体排序的数组类型再乘以该数组类型的长度进行遍历；
Swap是博主定义的用来进行交换的函数，实现如下
1. void Swap(char* buf1, char* buf2, int size)//交换arr[j],arr[j+1]这两个元素 2. { 3. int i = 0; 4. char tmp = 0; 5. for (i = 0; i < size; i++) 6. { 7. tmp = *buf1; 8. *buf1 = *buf2; 9. *buf2 = tmp; 10. buf1++; 11. buf2++; 12. } 13. }
由于强制转换为了char*类型，所以不能直接交换，应一个一个交换，交换size次，原理如下图
完整实现代码如下
1. void Swap(char* buf1, char* buf2, int size)//交换arr[j],arr[j+1]这两个元素 2. { 3. int i = 0; 4. char tmp = 0; 5. for (i = 0; i < size; i++) 6. { 7. tmp = *buf1; 8. *buf1 = *buf2; 9. *buf2 = tmp; 10. buf1++; 11. buf2++; 12. } 13. } 14. 15. void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*)) 16. { 17. int i = 0; 18. //趟数 19. for (i = 0; i < num - 1; i++) 20. { 21. int j = 0; 22. //一趟内部比较的对数 23. for (j = 0; j < num - 1 - i; j++) 24. { 25. //假设需要升序cmp返回>0，交换 26. if (cmp((char*)base+j*size, (char*)base+(j+1)*size)>0)//两个元素比较，需要将arr[j],arr[j+1]的地址要传给cmp 27. { 28. //交换 29. Swap((char*)base + j * size, (char*)base + (j + 1) * size, size); 30. } 31. } 32. } 33. 34. } 35. 36. int cmp_int(const void* p1, const void* p2) 37. { 38. return (*(int*)p1 - *(int*)p2); 39. }
使用如下
1. void test3() 2. { 3. int arr[10] = { 3,1,5,2,4,7,9,6,8,0 }; 4. int sz = sizeof(arr) / sizeof(arr[0]); 5. bubble_sort(arr, sz, sizeof(arr[0]), cmp_int); 6. } 7. int main() 8. { 9. test3(); 10. return 0; 11. }
关于结构体类型的排序，博主这里就不讲解了，代码如下
1. void Swap(char* buf1, char* buf2, int size)//交换arr[j],arr[j+1]这两个元素 2. { 3. int i = 0; 4. char tmp = 0; 5. for (i = 0; i < size; i++) 6. { 7. tmp = *buf1; 8. *buf1 = *buf2; 9. *buf2 = tmp; 10. buf1++; 11. buf2++; 12. } 13. } 14. 15. void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*)) 16. { 17. int i = 0; 18. //趟数 19. for (i = 0; i < num - 1; i++) 20. { 21. int j = 0; 22. //一趟内部比较的对数 23. for (j = 0; j < num - 1 - i; j++) 24. { 25. //假设需要升序cmp返回>0，交换 26. if (cmp((char*)base+j*size, (char*)base+(j+1)*size)>0)//两个元素比较，需要将arr[j],arr[j+1]的地址要传给cmp 27. { 28. //交换 29. Swap((char*)base + j * size, (char*)base + (j + 1) * size, size); 30. } 31. } 32. } 33. 34. } 35. 36. struct Stu 37. { 38. char name[20]; 39. int age; 40. }; 41. 42. 43. 44. int cmp_stu_by_name(const void* p1, const void* p2) 45. { 46. return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name); 47. } 48. 49. 50. void test() 51. { 52. struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 50},{"wangwu", 15} }; 53. int sz = sizeof(arr) / sizeof(arr[0]); 54. printf("%d\n", sizeof(struct Stu)); 55. bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_name); 56. } 57. 58. 59. 60. int main() 61. { 62. test(); 63. return 0; 64. }
后续博主还会讲解关于指针和数组面试题的解析，想要了解的宝子们记得关注博主后续动态哦！
