深圳幻海软件技术有限公司 欢迎您！
更多

C语言-qsort函数详解

2023-03-30

int void char
目录一.qsort函数是什么 二.使用qsort排序-以升序为例    关于void*型指针：1.整形数组排序2.字符数组排序3.字符指针数组排序4.结构体数组排序5.浮点型数组排序三.使用冒泡排序思想模拟实现qsort函数1.什么是冒泡排序：&nb

目录

一.qsort函数是什么

 二.使用qsort排序-以升序为例

      关于void*型指针：

1.整形数组排序

2.字符数组排序

3.字符指针数组排序

4.结构体数组排序

5.浮点型数组排序

三.使用冒泡排序思想模拟实现qsort函数

1.什么是冒泡排序：

 2.冒泡排序代码

3. 使用冒泡排序思想模拟实现qsort函数

一.qsort函数是什么

我们可以使用  搜索库函数网址或者MSDN软件进行查找。

qsort()函数：快速排序的函数  -引用stdlib.h头文件

参数说明：
void qsort ( 

    void* base, //要排序的目标数组
    size_t num,     //待排序的元素个数
    size_t width,    //一个元素的大小，单位是字节
    int(*cmp)(const void* e1, const void* e2)

);        

其中cmp是函数指针，cmp指向的是：排序时，用来比较两个元素的函数。需要自己编写。

返回值：

        

 二.使用qsort排序-以升序为例

关于void*型指针：

  void*：无具体类型的指针   能够接收任意类型的地址
 缺点：不能进行运算。不能+-整数，不能解引用

  1. int a  = 0;
  2. float f = 5.5f;
  3. void* p1 = &a;
  4. void* p2 = &f;
  5. p1 = p1+1;    //err

1.整形数组排序

注意：

1.比较函数的参数类型为void* ，我们要进行强制类型转换！且要解引用才能得到对应的值！ 

2.若我们想排成降序，只需要写成e2-e1即可

  1. void Print(int* arr, int sz)
  2. {
  3. int i = 0;
  4. for (i = 0; i < sz; i++)
  5. {
  6. printf("%d ", *(arr + i));
  7. }
  8. printf("\n");
  9. }
  10. //比较整形
  11. //注意类型时void* 所以要强制类型转化，还要解引用才是对应的值！！！
  12. int cmp_int(const void* e1, const void* e2)
  13. {
  14. return *(int*)e1 - *(int*)e2;
  15. }
  16. void test1()
  17. {
  18. int arr[] = { 9,8,7,6,7,5,4,8 };
  19. int sz = sizeof(arr) / sizeof(arr[0]);
  20. qsort(arr, sz, sizeof(arr[0]), cmp_int);
  21. Print(arr, sz);
  22. }

2.字符数组排序

注意使用sizeof()操作符和strlen()函数的区别

  1. //注意要要强制类型转换！！ 要解引用！！！  本质上是比较Ascii值
  2. int cmp_char(const void* e1, const void* e2)
  3. {
  4.     return *(char*)e1 - *(char*)e2;
  5. }
  6. void test4()
  7. {
  8. char arr[] ="mango";
  9.     //若使用sizeof计算长度：
  10. //int sz = sizeof(arr) / sizeof(arr[0]);//6
  11. //qsort(arr, sz-1, sizeof(arr[0]), cmp_float);
  12.     //因为sizeof把\0也算进去了，所以计算出来的值比字符串本身长度多1
  13.     
  14.     int sz = strlen(arr);//5
  15.     qsort(arr, sz, sizeof(arr[0]), cmp_char);
  16. printf("%s\n",arr);
  17. }

3.字符指针数组排序

先看看下面这段程序有没有问题？

  1. int cmp_chars(const void* e1, const void* e2)
  2. {
  3. return strcmp((char*)e1, *(char*)e2);
  4. }
  5. void test2()
  6. {
  7.  char* arr1 = "abc";
  8.  char* arr2 = "wcad";
  9.  char* arr3 = "cab";
  10.  char* p[3] = { arr1,arr2,arr3 };
  11. int sz = sizeof(p) / sizeof(p[0]);
  12. qsort(p, sz, sizeof(p[0]), cmp_chars);
  13. int i = 0;
  14. for (i = 0; i < sz; i++)
  15. {
  16. printf("%s\n", p[i]);
  17. }
  18. }

 打印出来发现：结果是错误的！

 ->调试后发现：e2存放的是p的地址（char**类型），e1存放的是p指向的下一个元素的地址（char**类型）        

对于这种写法，传进去的是p的地址，strcmp()会将p地址对应的内容转化成字符串，也就是将p中arr1，arr2，arr3的地址转化成字符串

实际上应该传p地址空间中arr1，arr2的地址，这样strcmp()才能找到arr1和arr2对应的字符串，因此得先把e1，e2转化成char**，这样解引用以后才是一个char*的地址

原因：把p传给qsort，p是数组名->首元素地址，元素类型为char*>，所以p的类型为：char**类型。  所以e1 和e2也要强制类型转化为char**，解引用e1，e2才是对应字符串的地址！

正解： 

  1. int cmp_chars(const void* e1, const void* e2)
  2. {
  3. return strcmp(*(char**)e1, *(char**)e2);
  4. }
  5. void test2()
  6. {
  7.  char* arr1 = "abc";
  8.  char* arr2 = "wcad";
  9.  char* arr3 = "cab";
  10.  char* p[3] = { arr1,arr2,arr3 };
  11. int sz = sizeof(p) / sizeof(p[0]);
  12. qsort(p, sz, sizeof(p[0]), cmp_chars);
  13. int i = 0;
  14. for (i = 0; i < sz; i++)
  15. {
  16. printf("%s\n", p[i]);
  17. }

4.结构体数组排序

比较年龄->实际比较的是整形

比较名字->实际比较的是字符串->使用strcmp函数，不能使用 == 判断

  1. struct Stu
  2. {
  3. int age;
  4. char name[20];
  5. };
  6. //比较结构体中元素的年龄
  7. int cmp_age(const void* e1, const void* e2)
  8. {
  9. //本质是比较整形
  10. return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
  11. }
  12. //比较名字
  13. int cmp_name(const void* e1, const void* e2)
  14. {
  15. //本质是字符串比较->使用strcmp函数
  16. return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
  17. }
  18. void test2()
  19. {
  20. //创建结构体数组，用大括号初始化
  21. struct Stu s[3] = { {19,"Mango"},{18,"Lemon"},{20,"Hello"} };
  22. int sz = sizeof(s) / sizeof(s[0]);
  23. //以年龄排
  24. qsort(s, sz, sizeof(s[0]), cmp_age);
  25. printf("%s %d ",s[0].name,s[0].age);
  26. printf("%s %d ", s[1].name, s[1].age);
  27. printf("%s %d ", s[2].name, s[2].age);
  28. printf("\n");
  29. //以姓名排
  30. qsort(s, sz, sizeof(s[0]), cmp_name);
  31. printf("%s %d ", s[0].name, s[0].age);
  32. printf("%s %d ", s[1].name, s[1].age);
  33. printf("%s %d ", s[2].name, s[2].age);
  34. printf("\n");
  35. }

5.浮点型数组排序

注意：比较函数中，返回类型是int，最后相减的值要强制类型转化为int ，但这也会造成错误，建议使用方法2.

  1. //写法1：可能会出错
  2. // 原因： 0.2 -0.1 = 0.1 强制类型转化为int后 结果为0
  3. //int cmp_float(const void* e1, const void* e2)
  4. //{
  5. ////返回类型是int  所以相减后的结果要强制类型转化
  6. //return (int)(*(float*)e1 - *(float*)e2);
  7. //}
  8.  
  9. //写法2：对应上qsort的返回值
  10. int cmp_float(const void* e1, const void* e2)
  11. {
  12. if ((*(float*)e1 - *(float*)e2) > 0.00000)
  13. return 1;
  14. else if ((*(float*)e1 - *(float*)e2) == 0.000000)
  15. return 0;
  16. else
  17. return -1;
  18. }
  19. void test3()
  20. {
  21. float arr[5] = { 5.01f,5.01f,0.02f,0.01f,5.001f };
  22. int sz = sizeof(arr) / sizeof(arr[0]);
  23. qsort(arr, sz, sizeof(arr[0]), cmp_float);
  24. int i = 0;
  25. for (i = 0; i < sz; i++)
  26. {
  27. printf("%f ", arr[i]);
  28. }
  29. }

三.使用冒泡排序思想模拟实现qsort函数

1.什么是冒泡排序：

主要思想：相邻的两个元素进行比较 

 

 对于冒泡排序： n个元素 共进行n-1趟冒泡排序。一趟可以使一个元素在特定位置上，每趟排序可以少比较一个元素

但是冒泡排序只能排序整形

 2.冒泡排序代码

  1. void BubbleSort(int* arr, int sz)
  2. {
  3. int i = 0;
  4. int j = 0;
  5. //共进行sz-1趟
  6. for (i = 0; i < sz-1; i++)
  7. {
  8. int flag = 1;//每一趟进来都假设有序
  9.         // 每一趟
  10. for (j = 0; j < sz - 1 - i; j++)
  11. {
  12. if (arr[j] > arr[j + 1])
  13. {
  14. int tmp = arr[j];
  15. arr[j] = arr[j + 1];
  16. arr[j + 1] = tmp;
  17. flag = 0;
  18. }
  19. }
  20.         //若falg还是1，说明没有交换->已经有序了break退出
  21. if (flag == 1)
  22. {
  23. break;
  24. }
  25. }
  26. }
  27. int main()
  28. {
  29. int arr[10] = { 2,3,6,7,9,0,0,3,2,10 };
  30. int sz = sizeof(arr) / sizeof(arr[0]);
  31. BubbleSort(arr, sz);
  32. return 0;
  33. }

3. 使用冒泡排序思想模拟实现qsort函数

qsort库函数使用的是什么参数，我们设计的函数就使用什么参数！

  

1.为何将base强制类型转化为char*型指针：

原因：char* 指针+1跳过一个字节，+width：跳过width个字节，指向下一个元素。转化为其他类型不合适

2. 交换函数：还要把宽度（每个元素所占字节数）传过去
因为交换的时候是传地址，所以要知道元素的宽度，一个字节一个字节的交换 ，这样也证明了使用char*指针的好处！

3.(char*)base + j * width, (char*)base + (j + 1) * width,

  当j = 0时：比较的是第一个元素和第二个元素
   j = 1时，比较的是第二个元素和第三个元素
    ....  很妙的写法

  1. //交换 --一个字节一个字节的交换，共交换width次
  2. void Swap(char* buf1, char* buf2, size_t width)
  3. {
  4. size_t i = 0;
  5. for (i = 0; i < width; i++)
  6. {
  7. char tmp = *buf1;
  8. *buf1 = *buf2;
  9. *buf2 = tmp;
  10. buf1++;
  11. buf2++;
  12. }
  13. }
  14. void my_BubbleSort(void* base, size_t num,size_t width, int(*cmp)(const void* e1, const void* e2))
  15. {
  16. //冒泡排序
  17. //若要排序n个元素，只需要进行n-1趟
  18. //每一趟可以少比较一个元素，每一趟可以使一个元素在确定的位置上
  19. //num：要排序元素的个数 类型是size_t 
  20.     //num是无符号数 防止产生警告 所以i和j也定义为size_t
  21.     // size_t == unsigned int 
  22. size_t i = 0;
  23. size_t j = 0;
  24.  
  25. //共进行num-1趟
  26. for (i = 0; i < num; i++)
  27. {
  28. //每一趟
  29. for (j = 0; j < num - 1 - i; j++)
  30. {
  31. //比较
  32. //传地址   
  33. //相邻两个元素比较   width:宽度，每个元素所占字节
  34. //排成升序
  35. if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
  36. {
  37. //交换两数
  38. Swap( (char*)base + j * width, (char*)base + (j + 1) * width, width );
  39. }
  40. }
  41. }
  42. }

当然 ，交换也可以使用库函数memcpy

dest：目标空间 

 src：要拷贝到目标空间的字符 -因为不作修改，所以可以用const修饰

count：字节数

  1. char tmp [30];    //防止结构体类型之类的类型    临时空间
  2. memcpy(tmp, (char*)base + j * size, size); 
  3. memcpy( (char*)base + j * size,  (char*)base + (j + 1) * size, size);
  4. memcpy( (char*)base + (j + 1) * size, tmp, size);

 如果文章对你有帮助的，欢迎大佬们点个赞留言呀！如果有错误的话，请评论告知！

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览42515 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪