整型数组的排序

废话不多说，我们直接开始测试整型数组的排序

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. }

后续博主还会讲解关于指针和数组面试题的解析，想要了解的宝子们记得关注博主后续动态哦！

指针进阶（二）（下）

整型数组的排序

结构题排序

按年龄排序

按名字排序

模拟实现qsort函数（冒泡排序）

热门文章

最新文章

相关电子书