AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【进阶C语言】排序函数（qsort）与模拟实现（回调函数的实例）

2023-10-21 51
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 回调函数为C语言重要知识点，以函数指针为主要知识；下面介绍回调函数的定义、回调函数的库函数举例即库函数模拟实现。

一、回调函数

1.回调函数定义

      回调函数就是一个通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。


     回调函数不是由该函数的实现方直接调用，而是在特定的事件或条件发生时由另外的一方调用的，用于对该事件或条件进行响应。

    总结：被函数指针调用的函数


2.回调函数机制实例

在进阶指针1的函数指针数组中，完成了计数器的实现，现在我们再用回调函数的方法改进，先看    

 原代码：

#include<stdio.h>
void menu()
{
  printf("****************************\n");
  printf("***  1. add      2. sub  ***\n");
  printf("***  3. mul      4. div  ***\n");
  printf("***  0. exit             ***\n");
  printf("****************************\n");
}
//加法
int Add(int x, int y)
{
  return x + y;
}
//减法
int Sub(int x, int y)
{
  return x - y;
}
//乘法
int Mul(int x, int y)
{
  return x * y;
}
//除法
int Div(int x, int y)
{
  return x / y;
}
int main()
{
  int input = 0;
  int x = 0;
  int y = 0;
  int ret = 0;
  do
  {
    menu();
    printf("请选择:>");
    scanf("%d", &input);
    switch (input)
    {
    case 1:
      printf("请输入2个操作数:");
      scanf("%d %d", &x, &y);
      ret = Add(x, y);
      printf("ret = %d\n", ret);
      break;
    case 2:
      printf("请输入2个操作数:");
      scanf("%d %d", &x, &y);
      ret = Sub(x, y);
      printf("ret = %d\n", ret);
      break;
    case 3:
      printf("请输入2个操作数:");
      scanf("%d %d", &x, &y);
      ret = Mul(x, y);
      printf("ret = %d\n", ret);
      break;
    case 4:
      printf("请输入2个操作数:");
      scanf("%d %d", &x, &y);
      ret = Div(x, y);
      printf("ret = %d\n", ret);
      break;
    case 0:
      printf("退出计算器\n");
      break;
    default:
      printf("选择错误, 重新选择\n");
      break;
    }
  } while (input);
  return 0;
}

 改进方向：

 可以发现，在case部分，很多代码都是重复的，显得冗余；上文使用函数指针数组将这些重复的包含了起来，实现了简洁的操作。

  接下来，我们使用函数指针的机制再次修改，使其更加简便。

   改进思路：

第一步：

image.png

第二步：初步改进后的代码

case 1:
  calc(Add);
  break;
case 2:
  calc(Sub);
  break;
case 3:
  calc(Mul);
  break;
case 4:
  calc(Div);
  break;
case 0:
  printf("退出计算器\n");
  break;
default:
  printf("选择错误, 重新选择\n");
  break;

将每个功能函数的地址传给一个通用的函数。

第三步：通用函数的实现（利用回调机制）

void calc(int (*pf)(int,int))//用函数指针接收函数地址
{
  int x = 0;
  int y = 0;
  int ret = 0;
  printf("请输入两个数>:");
  scanf("%d%d",&x,&y);
  ret = pf(x,y);//通过函数指针调用
  printf("%d\n",ret);
}

执行点：函数指针可以接收函数的地址，并且可以通过函数指针变量可以直接调用函数，被调用的函数称为回调函数。

第四步：程序运行图解

image.png

完整代码展示：

#include<stdio.h>
void menu()
{
  printf("****************************\n");
  printf("***  1. add      2. sub  ***\n");
  printf("***  3. mul      4. div  ***\n");
  printf("***  0. exit             ***\n");
  printf("****************************\n");
}
//加法
int Add(int x, int y)
{
  return x + y;
}
//减法
int Sub(int x, int y)
{
  return x - y;
}
//乘法
int Mul(int x, int y)
{
  return x * y;
}
//除法
int Div(int x, int y)
{
  return x / y;
}
void calc(int (*pf)(int,int))//用函数指针接收函数地址
{
  int x = 0;
  int y = 0;
  int ret = 0;
  printf("请输入两个数>:");
  scanf("%d%d",&x,&y);
  ret = pf(x,y);//通过函数指针调用
  printf("%d\n",ret);
}
int main()
{
  int input = 0;
  do
  {
    menu();
    printf("请选择:>");
    scanf("%d", &input);
    switch (input)
    {
    case 1:
      calc(Add);
      break;
    case 2:
      calc(Sub);
      break;
    case 3:
      calc(Mul);
      break;
    case 4:
      calc(Div);
      break;
    case 0:
      printf("退出计算器\n");
      break;
    default:
      printf("选择错误, 重新选择\n");
      break;
    }
  } while (input);
  return 0;
}

上述就是回调函数的介绍和一个简单的实例，下面库函数的实现也是利用了回调函数的机制。

二、排序函数qsort

为了对比出qsort，我们先来重温一遍冒泡排序。

1.冒泡排序

 将一个数组逆序：

#include<stdio.h>
my_bubble(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;
      }
    }
  }
}
print_bubble(int arr[],int sz)
{
  int i = 0;
  for (i=0;i<sz;i++)
  {
    printf("%d ",arr[i]);
  }
  printf("\n");
}
int main()
{
  int arr[] = {10,9,8,7,6,5,4,3,2,1};
  int sz = sizeof(arr) / sizeof(arr[0]);
  print_bubble(arr,sz);
  my_bubble(arr,sz);//将数组升序
  print_bubble(arr,sz);
  return 0;
}

上述就是冒泡排序的代码

image.png

由此可知，冒泡排序的局限性，所以我们下面介绍万能排序函数--qsort

2.qsort的介绍

  函数基础原型：

image.png

需要包含头文件#include<stdlib.h>


  qsort功能介绍：


该函数是一个库函数，可以排序任意数据类型的数据（数组）；底层逻辑采用的是快速排序


  参数介绍：


前三个参数：


void* base：待排序数据的第一个元素的地址

size_t num：待排序数据元素的个数

size_t size：待排序数组中一个元素的大小，单位是字节


第四个参数：


（1）int (*compar)(const void*，const void*)：这是一个函数指针参数，变量为：compar

（2）compar是一个比较函数，作用是比较两个数据的大小


compar函数的要求：

image.png

（1）compar函数是需要用户（需要排序的程序员）自己完成的函数


（2）要求：对两个数进行比较


第一个参数指向的值>第二个，返回>0的数字

第一个参数指向的值=第二个，返回=0的数字

第一个参数指向的值<第二个，返回<0的数字


（3）函数的返回值类型必须是：int


（4）两个参数类型必须是：void*；


目的：可以接收任意类型数据的地址


3.qsort函数的使用

将上述的数字逆序


  主函数传参部分：

int my_compar(const void* e1, const void* e2)
{
  //需要自己完成的比较函数
}
int main()
{
  int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  print_bubble(arr, sz);
  //可以直接调用库函数进行排序
  qsort(arr,sz,sizeof(arr[0]),my_compar);
  print_bubble(arr, sz);
  return 0;
}

完成函数部分：

int my_compar(const void* e1, const void* e2)
{
  //需要自己完成的比较函数
  return *((int*)e1) - *((int*)e2);
}

   （1）void*可以兼容任意类型的地址；但是不能进行解引用和+\-操作

（2）根据自己的需要排序的数据类型完成该部分函数，该函数便是回调函数

整体实现：

#include<stdio.h>
#include<stdlib.h>
print_bubble(int arr[], int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}
//排序整形数据
int my_compar(const void* e1, const void* e2)
{
  return *((int*)e1) - *((int*)e2);
}
int main()
{
  int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  print_bubble(arr, sz);
  qsort(arr,sz,sizeof(arr[0]),my_compar);
  print_bubble(arr, sz);
  return 0;
}

结果展示：

image.png

排序结构体数据类型

  结构体中的整形数据（年龄）：

#include<stdio.h>
#include<stdlib.h>
struct Stu
{
  char name[20];
  int age;
  int s;
};
print_bubble(struct Stu* arr, int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%s,%d ", (arr[i]).name,(arr[i]).age);
  }
  printf("\n");
}
//排序结构中的年龄（整形）
int compar_Stu_age(const void* e1,const void* e2)
{
  return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
int main()
{
  struct Stu arr[] = { {"张三",19},{"李四",22},{"王五",20}};
  int sz = sizeof(arr) / sizeof(arr[0]);
  printf("年龄从小到大排序：\n");
  print_bubble(arr, sz);
  qsort(arr, sz, sizeof(arr[0]), compar_Stu_age);
  print_bubble(arr, sz);
  return 0;
}

结果展示：

image.png

结构体中字符的排序（名字）：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Stu
{
  char name[20];
  int age;
  int s;
};
print_bubble(struct Stu* arr, int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%s,%d ", (arr[i]).name, (arr[i]).age);
  }
  printf("\n");
}
int compar_Stu_name(const void* e1, const void* e2)
{
    //字符串比较需要用该函数
  return strcmp(((struct Stu*)e1)->name ,((struct Stu*)e2)->name);
}
int main()
{
  struct Stu arr[] = { {"张三",19},{"李四",22},{"王五",20} };
  int sz = sizeof(arr) / sizeof(arr[0]);
  printf("名字按字典排序：\n");
  print_bubble(arr, sz);
  qsort(arr, sz, sizeof(arr[0]), compar_Stu_name);
  print_bubble(arr, sz);
  return 0;
}

结果展示：

image.png

以上就是qsort函数使用的一些例子

库函数qsort使用步骤：

三、模拟实现qsort

模拟思路：底层使用【冒泡排序】的算法模拟实现qsort，使得可以排序任意类型的数据。所以我们在冒泡排序的基础上进行改造。

1.改造方向

对比方向：

image.png

2.分部改造

（1）改造参数

//改造前的
void bubble_sort(int arr[], int sz)
//改造后的参数写法
void bubble_qsort(void* base,size_t num,size_t size,int (*cmp)(const void* e1,const void* e2))
void bubble_sort(int arr[], int sz)
//改造后的参数写法
void bubble_qsort(void* base,size_t num,size_t size,int (*cmp)(const void* e1,const void* e2))
void bubble_sort(int arr[], int sz)
//改造后的参数写法
void bubble_qsort(void* base,size_t num,size_t size,int (*cmp)(const void* e1,const void* e2))

第四个参数：是一个函数指针，用来接收函数的地址。该函数是一个比较函数，由使用者撰写，用来比较两个数据的大小，并传参。

改造后：

image.png

比较函数（cmp_int）:

//用来比较整形数据
int cmp_int(const void* e1,const void* e2)
{
  return *((int*)e1) - *((int*)e2);
}

（1）e1是一个指针，存放了一个要比较的元素的地址

        e2是一个指针，存放了一个要比较的元素的地址

（2）e1指向的元素>e2指向的元素，返回>0的数字

        e1指向的元素==e2指向的元素，返回0

        e1指向的元素<e2指向的元素，返回<0的数字


参数意义：


（1）void* base：待排序数据的首元素地址


（2）size_t num：无符号整形，num为待排序数据的个数


（3）size_t size：无符号整形，待排序数据的一个元素的大小。单位：字节


（4）cmp：函数指针


（2）改造“两个数据的比较”


我们有自己撰写的“比较函数”，所以肯定是直接调用该函数即可。

if(cmp()>0)
//根据返回的结果判断是否需要交换

问题：比较的是两个相邻的元素，那怎么找到两个相邻元素的地址呢？

image.png

1.void*的指针不可以进行解引用操作和+1或者-1操作

2.需要将void*强转之后才能进行操作；因为不知道是比较什么数据类型，所以我们可以强转成char*

处理办法：

image.png

base的地址就是元素的起始地址

比较方法：

image.png

交换两个数据：

当两个数据完成比较之后，满足条件就要交换

bubble_qsort函数： 

void bubble_qsort(void* base,size_t num,size_t size,int (*cmp)(const void* e1,const void* e2))
{
  int i = 0;
  for (i=0;i<num-1;i++)
  {
    int j = 0;
    for (j=0;j<num-1-i;j++)
    {
      //冒泡排序的比较
      //if(arr[j]>arr[j+1])
      if( cmp((char*)base+j*size,(char*)base+(j+1)*size) >0)
      {
        //交换
        swap((char*)base + j * size, (char*)base + (j + 1) * size,size);
      }
    }
  }
}

交换部分：

image.png

依旧是将相邻两个数据的起始地址作为交换；并且多了一个参数：size

交换函数：

void swap(char* buf1,char* buf2,size_t size)
{
  int i = 0;
  for (i=0;i<size;i++)
  {
    char* tmp = *buf1;
    *buf1 = *buf2;
    *buf2 = tmp;
    buf1++;
    buf2++;
  }
}

image.png

分部思路完成

3.整体思路步骤

（1）整体代码（交换整形数据）

#include<stdio.h>
//模拟内部交换的代码
void swap(char* buf1, char* buf2, size_t size)
{
  int i = 0;
  for (i = 0; i < size; i++)
  {
    char tmp = *buf1;
    *buf1 = *buf2;
    *buf2 = tmp;
    buf1++;
    buf2++;
  }
}
//模拟内部排序的代码
void bubble_qsort(void* base,size_t num,size_t size,int (*cmp)(const void* e1,const void* e2))
{
  int i = 0;
  for (i=0;i<num-1;i++)
  {
    int j = 0;
    for (j=0;j<num-1-i;j++)
    {
      if( cmp((char*)base+j*size,(char*)base+(j+1)*size) >0)
      {
        //交换
        swap((char*)base + j * size, (char*)base + (j + 1) * size,size);
      }
    }
  }
}
//打印函数
void print_bubble(int arr[],int sz)
{
  int i = 0;
  for (i=0;i<sz;i++)
  {
    printf("%d ",arr[i]);
  }
  printf("\n");
}
//用来比较整形数据（个人撰写）
int cmp_int(const void* e1,const void* e2)
{
  return *((int*)e1) - *((int*)e2);
}
int main()
{
  int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  print_bubble(arr,sz);
  bubble_qsort(arr,sz,sizeof(arr[0]),cmp_int);
  print_bubble(arr,sz);
  return 0;
}

（2）整体思路剖析

image.png

（3）整体步骤

待排序内容、传参：

int main()
{
  int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  print_bubble(arr,sz);
  bubble_qsort(arr,sz,sizeof(arr[0]),cmp_int);
  print_bubble(arr,sz);
  return 0;
}

比较函数：

//用来比较整形数据（个人撰写）
int cmp_int(const void* e1,const void* e2)
{
  return *((int*)e1) - *((int*)e2);
}

排序函数：

//模拟内部排序的代码
void bubble_qsort(void* base,size_t num,size_t size,int (*cmp)(const void* e1,const void* e2))
{
  int i = 0;
  for (i=0;i<num-1;i++)
  {
    int j = 0;
    for (j=0;j<num-1-i;j++)
    {
      if( cmp((char*)base+j*size,(char*)base+(j+1)*size) >0)
      {
        //交换
        swap((char*)base + j * size, (char*)base + (j + 1) * size,size);
      }
    }
  }
}

交换函数：

//模拟内部交换的代码
void swap(char* buf1, char* buf2, size_t size)
{
  int i = 0;
  for (i = 0; i < size; i++)
  {
    char tmp = *buf1;
    *buf1 = *buf2;
    *buf2 = tmp;
    buf1++;
    buf2++;
  }
}

以上qsort函数的模拟已完成。如果需要排序其他的数据类型，只需要修改待排序数据、传参和比较函数即可

文章标签：
C语言
程序员
算法
关键词：
C语言函数
C语言qsort
C语言排序
C语言进阶
C语言回调函数
小小娥子
目录
相关文章
ephemerals__
|
2天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（上）（c语言实现）（附源码）
本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
ephemerals__
26 8
ephemerals__
|
2天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（下）（c语言实现）（附源码）
本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
ephemerals__
20 7
c的前世今生
|
13天前
|
存储 算法 程序员
C语言：库函数
C语言的库函数是预定义的函数，用于执行常见的编程任务，如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作，提高开发效率。C标准库提供了丰富的函数，满足各种需求。
c的前世今生
19 1
ephemerals__
|
18天前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件，并通过求阶乘、打印整数每一位和求斐波那契数等实例，展示了递归的应用。递归的核心在于将大问题分解为小问题，但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点，提醒读者在实际编程中合理使用递归。
ephemerals__
45 7
ephemerals__
|
16天前
|
存储 C语言
【c语言】字符串函数和内存函数
本文介绍了C语言中常用的字符串函数和内存函数，包括`strlen`、`strcpy`、`strcat`、`strcmp`、`strstr`、`strncpy`、`strncat`、`strncmp`、`strtok`、`memcpy`、`memmove`和`memset`等函数的使用方法及模拟实现。文章详细讲解了每个函数的功能、参数、返回值，并提供了具体的代码示例，帮助读者更好地理解和掌握这些函数的应用。
ephemerals__
15 0
ephemerals__
|
16天前
|
C语言
【c语言】qsort函数及泛型冒泡排序的模拟实现
本文介绍了C语言中的`qsort`函数及其背后的回调函数概念。`qsort`函数用于对任意类型的数据进行排序，其核心在于通过函数指针调用用户自定义的比较函数。文章还详细讲解了如何实现一个泛型冒泡排序，包括比较函数、交换函数和排序函数的编写，并展示了完整的代码示例。最后，通过实际运行验证了排序的正确性，展示了泛型编程的优势。
ephemerals__
15 0
白子寰
|
28天前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
白子寰
31 3
morixinguan
|
C语言 C++ Unix
深入浅出剖析C语言函数指针与回调函数(三)
前面两篇文章: http://blog.csdn.net/morixinguan/article/details/65494239 http://blog.csdn.net/morixinguan/article/details/65938128 在UNix多线程编程中，我们会使用到以下函数:...
morixinguan
1199 0
morixinguan
|
Linux C语言
深入浅出剖析C语言函数指针与回调函数(二)
上一篇博文的地址: http://blog.csdn.net/morixinguan/article/details/65494239 这节，我们来看看函数指针与回调函数在Linux内核中的应用。
morixinguan
1040 0
morixinguan
|
C语言 开发者 Linux
深入浅出剖析C语言函数指针与回调函数(一)
关于静态库和动态库的使用和制作方法。 http://blog.csdn.net/morixinguan/article/details/52451612 今天我们要搞明白的一个概念叫回调函数。 什么是回调函数？ 百度的权威解释如下： 回调函数就是一个通过函数指针调用的函数。
morixinguan
1495 0