【指针进阶三】实现C语言快排函数qsort&回调函数

简介: 【指针进阶三】实现C语言快排函数qsort&回调函数

0. 经典快速排序算法-Quick_sort

先来手动实现一下Quick_sort 排序函数

#include<stdio.h>
void Swap(int* a, int* b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}
void Quick_sort(int* arr, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  int keyi = begin;
  int left = begin, right = end;
  while (left < right)
  {
    while (left < right && arr[right] >= arr[keyi])
    {
      right--;
    }
    while (left < right && arr[left] <= arr[keyi])
    {
      left++;
    }
    Swap(&arr[left], &arr[right]);
  }
  int meeti = left;
  Swap(&arr[keyi], &arr[meeti]);
  Quick_sort(arr, begin, meeti-1);
  Quick_sort(arr, meeti+1, end);
}
void Print(int* arr, int sz)
{
  for (int i = 0; i < sz; i++)
  {
    printf("%d\t", arr[i]);
  }
}
int main()
{
  int arr[5] = { 12,43,5,23,6 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  Quick_sort(arr, 0,sz-1);
  Print(arr, sz);
  return 0;
}

排序结果:


64afdf7823654046b9a8d6a8c2d76097.png


但是这里有一个问题: 如果下次我想对一个结构体进行排序,我对这个排序算法的改动就会非常大(几乎每一处都有改动),下面我也给出排序结构体相应的代码实现,给各位看看。

#include<stdio.h>
#include<string.h>
typedef struct stu
{
  char name[20];
  int age;
}stu;
void Swap(stu* a,stu* b)
{
  stu temp = *a;
  *a = *b;
  *b = temp;
}
void Quick_sort(stu* ps, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  int keyi = begin;
  int left = begin, right = end;
  while (left < right)
  {
    while (left < right && strcmp(ps[right].name, ps[keyi].name) >= 0)
    {
      right--;
    }
    while (left < right && strcmp(ps[left].name, ps[keyi].name) <= 0)
    {
      left++;
    }
    Swap(&ps[left], &ps[right]);
  }
  int meeti = left;
  Swap(&ps[keyi], &ps[meeti]);
  Quick_sort(ps, begin, meeti - 1);
  Quick_sort(ps, meeti+1, end);
}
void Print(stu* ps, int sz)
{
  for (int i = 0; i < sz; i++)
  {
    printf("%s\n", ps[i].name);
  }
}
int main()
{
  stu s[3] = { {"张三",18},{"李四",20},{"王五",19} };
  int sz = sizeof(s) / sizeof(s[0]);
  Quick_sort(s,0,sz-1);
  Print(s, sz);
  return 0;
}


排序结果:


266b9955a4334274845501204c21e086.png


由此我们就想:能不能设计出一个函数使得在给不同数据类型的元素进行排序时能够增加排序函数Quick_sort代码的复用性,因此,库函数qsort应运而生 ,那这个函数长什么样子呐?


1. qsort排序函数的基本介绍


qsort排序函数是C语言标准库里的函数,实现原理是快速排序算法,函数原型如下:


43d4b93c069944c8930efde888d39f8a.png


qsort函数的相关参数的介绍和意义:


头文件: #include<stdlib.h>

返回值: 无

void  base: 待排序数据元素的起始地址

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

size_t width:待排序数据元素所占的大小,单位是字节

int( * cmp)(const void*,const void*): 函数指针-比较数据元素大小的函数,排序依据

举个例子:  

#include<stdio.h>
#include<stdlib.h>
//以qsort库函数实现整型数组排序为例
int main()
{
  int arr[5] = { 12,43,5,23,6 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  qsort(arr, sz, sizeof(arr[0]), cmp);
  //arr:数组名,也是数组首元素的地址,数值上等于首元素中4个字节中地址最低的那个字节的地址
  //sz:数组arr的元素个数
  //sizeof(arr[0]):每一个数组元素所占的字节数
  //cmp_int:回调函数-比较数组元素的函数,根据调用者的需要自行实现
  Print(arr, sz);
  return 0;
}

先抛去qsort函数具体实现不谈,看到这里,你就知道了qsort函数的灵活性在于第四个参数(比较函数)是可以根据使用者的具体排序要求来自行设计。


2. 比较函数


比较函数的设计举例:整型数组,结构体数组等等


整型数组排序:(全部代码)


担心你看花函数之间的调用关系:给你个图理解一下

c4fa546cfd7c4f51abb5c917c6cb4386.png

#include<stdio.h>
#include<stdlib.h>
int cmp_int(const void* e1, const void* e2)
{
    //比较两个整型元素
  //void*是无具体类型的指针
  //void*的指针可以接收任意类型的地址,类似垃圾桶
  //void*的指针没有具体类型,不能+1-1(因为不知道加多少)
  //升序:
  return *(int*)e1 - *(int*)e2;
  //降序:
  //return *(int*)e2 - *(int*)e1;
}
void Print(int* arr, int sz)
{
  for (int i = 0; i < sz; i++)
  {
    printf("%d\t", arr[i]);
  }
}
void test1()
{
  int arr[6] = { 14,35,4,42,6,12 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  qsort(&arr[0], sz, sizeof(arr[0]), cmp_int);
  Print(arr, sz);
}
int main()
{
  test1();
  return 0;
}

由于void空类型的指针:


可以接收任何类型的指针

不能直接加减整数,使用前需要强转

因为cmp比较函数需要使用者自行设计,所以对于不同的使用者在qsort函数里传给cmp函数的参数类型可能是任何类型的指针,所以在cmp比较函数内得用void*类型的指针来接收,使用时只需将void* 类型的指针做出相应的强转即可。


排序结果:


8670c5f668994e46ac3a9da28086fe51.png


结构体数组排序:


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct stu
{
  char name[20];
  int age;
}stu;
int cmp_struct_by_name(const void* e1, const void* e2)
{
  return strcmp(((stu*)e1)->name, ((stu*)e2)->name);//妙哉之处
}
void Print(stu* ps, int sz)
{
  for (int i = 0; i < sz; i++)
  {
    printf("%s\n", ps[i].name);
  }
}
void test2()
{
  stu s[3] = { {"zhangsan",18},{"lisi",20},{"wangwu",19} };
  int sz = sizeof(s) / sizeof(s[0]);
  qsort(s,sz,sizeof(s[0]),cmp_struct_by_name);
  Print(s, sz);
}
int main()
{
  test2();
  return 0;
}

排序结果:


1a60ad288e264a17b4f80374dbb70b8a.png


比较字符串用strcmp函数,头文件#include<string.h>


妙哉之处:strcmp比较函数和规定的cmp比较函数的返回值的意义相同

返回值>0             elem1>elem2

返回值==0           elem1==elem2

返回值<0             elem1<elem2


a09567f1d216431899b7e07debe2d466.png

2. qsort函数的具体实现

学习qsort函数的具体实现,你将学到这个C语言库函数另一个绝妙的地方。

void Swap(char* buff1,char* buff2,int width)
{
  if (buff1 != buff2)
  {
    //way1
    //while (width--)
    //{
    //  char temp = *buff1;
    //  *buff1 = *buff2;
    //  *buff2 = temp;
    //  buff1++;
    //  buff2++;
    //way2
    for (int i = 0; i < width; i++)
    {
      char temp = *(buff1+i);
          *(buff1+i) = *(buff2+i);
          *(buff2+i) = temp;
    }
  }
}
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void*, const void*))
{
  int flag = 1;
  //趟数
  for (int i = 0; i < sz-1; i++)
  {
    for (int j = 0; j < sz - 1 - i; j++)
    {
      if (cmp((char*)base + j * width, (char*)base + (j+1) * width)>0)
      {
        Swap((char*)base + j * width, (char*)base + (j+1) * width, width);
        flag = 0;
      }
    }
    if (flag == 1) break;
  }
}

巧妙之处在于将实际参数void* 类型的base指针强转为char*类型。


类比int arr[5]={34,5,35,62,1};

Print(arr,5),这里的arr其实就是首元素的地址,在数值上和首元素4个字节中最低字节的地址是相同的,所以cmp函数的参数即使是char* 一个字节的地址,在cmp函数内同样可以强转为所需要的类型,进行解引用,拿到相应的字节数进行比较,这样就能做到在bubble_sort函数内得到统一,所以无论我们要对任何类型的数据进行排序,都可以直接调用bubble_sort函数,只需要更改cmp函数即可,这就增加了bubble_sort函数代码的复用性。


image.png


目录
打赏
0
0
0
0
3
分享
相关文章
|
1月前
|
指针的函数传参的详细讲解(一)
本文介绍了计算机内存管理与C语言中指针的基本概念及应用。从内存单元的划分到指针的定义,解释了指针作为地址的作用及其数据类型特性。文章通过代码示例详细说明了一级指针、二级指针的使用方法,以及`void*`指针的特点和限制。此外,还探讨了指针运算规则、函数指针传参解引用的原理,并结合链表实例分析了一级与二级指针在实际场景中的区别。最后附带两道指针练习题,帮助读者巩固理解。
32 0
一文彻底搞清楚C语言的函数
本文介绍C语言函数:函数是程序模块化的工具,由函数头和函数体组成,涵盖定义、调用、参数传递及声明等内容。值传递确保实参不受影响,函数声明增强代码可读性。君志所向,一往无前!
107 1
一文彻底搞清楚C语言的函数
|
6月前
|
【C语言程序设计——函数】亲密数判定(头歌实践教学平台习题)【合集】
本文介绍了通过编程实现打印3000以内的全部亲密数的任务。主要内容包括: 1. **任务描述**:实现函数打印3000以内的全部亲密数。 2. **相关知识**: - 循环控制和跳转语句(for、while循环,break、continue语句)的使用。 - 亲密数的概念及历史背景。 - 判断亲密数的方法:计算数A的因子和存于B,再计算B的因子和存于sum,最后比较sum与A是否相等。 3. **编程要求**:根据提示在指定区域内补充代码。 4. **测试说明**:平台对代码进行测试,预期输出如220和284是一组亲密数。 5. **通关代码**:提供了完整的C语言代码实现
120 24
|
6月前
|
【C语言程序设计——函数】递归求斐波那契数列的前n项(头歌实践教学平台习题)【合集】
本关任务是编写递归函数求斐波那契数列的前n项。主要内容包括: 1. **递归的概念**:递归是一种函数直接或间接调用自身的编程技巧,通过“俄罗斯套娃”的方式解决问题。 2. **边界条件的确定**:边界条件是递归停止的条件,确保递归不会无限进行。例如,计算阶乘时,当n为0或1时返回1。 3. **循环控制与跳转语句**:介绍`for`、`while`循环及`break`、`continue`语句的使用方法。 编程要求是在右侧编辑器Begin--End之间补充代码,测试输入分别为3和5,预期输出为斐波那契数列的前几项。通关代码已给出,需确保正确实现递归逻辑并处理好边界条件,以避免栈溢出或结果
305 16
【C语言程序设计——函数】分数数列求和2(头歌实践教学平台习题)【合集】
函数首部:按照 C 语言语法,函数的定义首部表明这是一个自定义函数,函数名为fun,它接收一个整型参数n,用于指定要求阶乘的那个数,并且函数的返回值类型为float(在实际中如果阶乘结果数值较大,用float可能会有精度损失,也可以考虑使用double等更合适的数据类型,这里以float为例)。例如:// 函数体代码将放在这里函数体内部变量定义:在函数体中,首先需要定义一些变量来辅助完成阶乘的计算。比如需要定义一个变量(通常为float或double类型,这里假设用float。
165 3
【C语言程序设计——函数】分数数列求和1(头歌实践教学平台习题)【合集】
if 语句是最基础的形式,当条件为真时执行其内部的语句块;switch 语句则适用于针对一个表达式的多个固定值进行判断,根据表达式的值与各个 case 后的常量值匹配情况,执行相应 case 分支下的语句,直到遇到 break 语句跳出 switch 结构,若没有匹配值则执行 default 分支(可选)。例如,在判断一个数是否大于 10 的场景中,条件表达式为 “num> 10”,这里的 “num” 是程序中的变量,通过比较其值与 10 的大小关系来确定条件的真假。常量的值必须是唯一的,且在同一个。
152 2
【C语言程序设计——函数】回文数判定(头歌实践教学平台习题)【合集】
算术运算于 C 语言仿若精密 “齿轮组”,驱动着数值处理流程。编写函数求区间[100,500]中所有的回文数,要求每行打印10个数。根据提示在右侧编辑器Begin--End之间的区域内补充必要的代码。如果操作数是浮点数,在 C 语言中是不允许直接进行。的结果是 -1,因为 -7 除以 3 商为 -2,余数为 -1;注意:每一个数据输出格式为 printf("%4d", i);的结果是 1,因为 7 除以 -3 商为 -2,余数为 1。取余运算要求两个操作数必须是整数类型,包括。开始你的任务吧,祝你成功!
124 1
C语言如何使用结构体和指针来操作动态分配的内存
在C语言中,通过定义结构体并使用指向该结构体的指针,可以对动态分配的内存进行操作。首先利用 `malloc` 或 `calloc` 分配内存,然后通过指针访问和修改结构体成员,最后用 `free` 释放内存,实现资源的有效管理。
660 13
C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
本文详细讲解了C语言中的指针,包括指针变量的定义与引用、指向数组及字符串的指针变量等。首先介绍了指针变量的基本概念和定义格式,随后通过多个示例展示了如何使用指针变量来操作普通变量、数组和字符串。文章还深入探讨了指向函数的指针变量以及指针数组的概念,并解释了空指针的意义和使用场景。通过丰富的代码示例和图形化展示,帮助读者更好地理解和掌握C语言中的指针知识。
389 4
|
9月前
|
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
105 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等