当前位置: 首页 > news >正文

C语言--模拟实现库函数qsort

什么是qsort

qsort是一个库函数,是用来排序的库函数,使用的是快速排序的方法(quicksort)
qsort的好处在于:
1,现成的
2,可以排序任意类型的数据

在之前我们已经学过一种排序方法:冒泡排序。排序的原理是两两相邻的元素进行比较。但是冒泡排序的缺陷就在于只能两两整型进行比较,可现实生活中很多东西的比较并不只是仅仅局限于数字的比较,比如名字的排序等等。
但是qsort就可以排序任意类型的数据
1,比较两个整数的大小(< > =)
2,比较两个字符串(strcmp)
3,比较两个结构体数据(学生:张三,李四,王五)

qsort的声明与参数

我们先来看C标准库里对qsort函数的描述

头文件

qsort需引用的头文件为 <stdlib.h>

#include <stdio.h>

声明

qsort函数的声明如下

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
{
}

参数

qsort函数的参数如下

base -- 指向了待排序数组的第一个元素
num -- 待排序的元素个数
size -- 每个元素的大小,单位是字节
cmp -- 指向一个函数,这个函数可以比较两个元素的大小

书写格式

我们以给一个数组按升序排序为例,看下面这段代码:

#include <stdio.h>
#include <stdlib.h>int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}void print(int arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d", arr[i]);}}
void test1()
{int arr[] = { 9,8,6,7,5,4,2,3,1 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_int);print(arr, sz);
}
int main()
{test1();return 0;
}

值得注意的是,其中的cmp_int函数是系统已经封装好了的一个函数,但是因为编译者在编译这个函数的时候,并不知道后来的人们使用这个qsort去排序什么类型的元素,所以用了void* 这样一个通用类型的指针
这就意味着void*这个指针可以存放任意数据类型的指针。

int main()
{int a = 0;int* p = &a;//通常写法char* p = &a;//编译器会报错,char*类型与a类型不匹配void* p = &a;//通用指针*p;//报错*(int*)p;//正确return 0;
}

为什么用void*指针来存放地址直接解引用会报错呢?这是因为系统在解引用操作时并不知道要访问几个字节,必须要强制类型转换才能正常解引用

测试qsort排序结构体

学习完了qsort函数的基本格式,我们现在来尝试运用一下它,以实现对结构体的排序为例:

以年龄升序排序

struct Stu
{char name[20];int age;
};
int cmp_stu_by_age(const void* p1, const void* p2)
{return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;
}
void test2()
{struct Stu s[] = { {"zhangsan",20},{"lisi",25},{"wangwu",15} };int sz = sizeof(s) / sizeof(s[0]);//按年龄来比较qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}
int main()
{test2();return 0;
}

我们用监视的方法来看一下排序的结果
图1

以姓名升序排序

如果我们要以姓名排序,要注意的是,姓名是一个字符串,而字符串是不能直接相减的,所以我们要使用另一个库函数—strcmp来进行比较,但是返回值类型仍然为整型,因为strcmp这个库函数的返回值类型就是整型,代码书写如下

struct Stu
{char name[20];int age;
};
int cmp_stu_by_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)->name,((struct Stu*)p2)->name);
}
void test2()
{struct Stu s[] = { {"zhangsan",20},{"lisi",25},{"wangwu",15} };int sz = sizeof(s) / sizeof(s[0]);//按姓氏来比较qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
}
int main()
{//test1();test2();return 0;
}

我们同样用监视的方法来看一下结果
图2
结果也是成功以姓名升序排列。

用冒泡排序来模拟实现

因为我们还没有学习快速排序的底层逻辑,所以本章我们先用冒泡排序的思想来实现一个类似于qsort这个函数功能的冒泡排序函数bubble_sort,效果是一样的。
在之前的文章里有专门的对于冒泡排序实现过程的讲解,这里不再过多赘述,直接上代码

void bubble_sort(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 temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}
int main()
{int arr[] = { 3,1,5,9,2,4,7,6,8,0 };//排序 - 升序//冒泡排序int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr,sz);//arr是数组首元素的地址int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

我们先来看以冒泡排序为原理实现的快排源码再逐一分析:

int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}void Swap(char* buf1, char* buf2,int width)
{int i = 0;for (i = 0; i < width; i++){char tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}
void bubble_sort(void* base, size_t num,size_t width, int(*cmp)(const void* p1, const void* p2))
{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 * width, (char*)base + (j + 1) * width) > 0){Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}
void test3()
{int arr[] = { 3,2,1,4,5,7,8,9,6 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);print(arr, sz);
}
int main()
{test3();return 0;
}

图解

我们来通过图文结合·进一步了解各部分的作用:
图3
通过图解应该能对该算法有更深一步的理解。

以上就是关于模拟实现库函数qsort(快排)的全部内容了,如有出入,欢迎指正。

相关文章:

C语言--模拟实现库函数qsort

什么是qsort qsort是一个库函数&#xff0c;是用来排序的库函数&#xff0c;使用的是快速排序的方法(quicksort)。 qsort的好处在于&#xff1a; 1&#xff0c;现成的 2&#xff0c;可以排序任意类型的数据。 在之前我们已经学过一种排序方法&#xff1a;冒泡排序。排序的原理…...

面向专业课教学和学习的《计算机数学》点播工具

本文是面向大学和高职的《计算机数学》课程的配套资料&#xff0c;全部为知识点或练习题的讲解视频&#xff0c;目的是如下2个场景&#xff1a; 1、专业课教师备课前&#xff0c;可以直接从本页的资源中选择&#xff0c;作为学生的预习资料 2、专业课教师上课过程中&#xff…...

域权限维持之创建DSRM后门

DSRM&#xff08;目录服务还原模式&#xff09;&#xff0c;在初期安装域控的时候会让我们设置DSRM的管理员密码&#xff0c;这个密码是为了在后期域控发生问题时修复、还原或重建活动目录。DSRM账户实际上是administrator账户&#xff0c;并且该账户的密码在创建之后很少使用。…...

【苹果内购支付】关于uniapp拉起苹果内购支付注意事项、实现步骤以及踩过的坑

前言 Hello&#xff01;又是很长时间没有写博客了&#xff0c;因为最近又开始从事新项目&#xff0c;也是第一次接触关于uniapp开发原生IOS应用的项目&#xff0c;在这里做一些关于我在项目中使用苹果内购支付所实现的方式以及要注意的事项&#xff0c;希望能给正在做uniapp开…...

一:BT、BLE版本说明及对比

蓝牙版本说明1.常见名词说明2.BT&BLE特性对比3.BT各版本对比4.BLE各版对比1.常见名词说明 名称说明BR(Basic Rate)基本码率EDR(Enhanced Data Rate)增强码率BLE(Bluetooth Low Energy)低功耗蓝牙HS(High Speed)高速蓝牙BT(BlueTooth)蓝牙技术LE(Low Energy)低能耗AFH(Adap…...

php宝塔搭建部署实战多模板cms管理系统源码

大家好啊&#xff0c;我是测评君&#xff0c;欢迎来到web测评。 本期给大家带来一套php开发的多模板cms管理系统源码。感兴趣的朋友可以自行下载学习。 技术架构 PHP7.0 nginx mysql5.7 JS CSS HTMLcnetos7以上 宝塔面板 文字搭建教程 下载源码&#xff0c;宝塔添加一…...

【数据结构初阶】手把手带你实现栈

前言 在进入数据结构初阶的学习之后&#xff0c;我们学习了顺序表和链表&#xff0c;当然栈也是一种特殊的数据结构&#xff0c;他的特点是后进先出。 栈的概念及结构 栈&#xff08;stack&#xff09;又名堆栈&#xff0c;它是一种运算受限的线性表。限定仅在表尾进行插入和删…...

liunx 端口号开放和关闭

1.先查看防火墙是否开启的状态&#xff0c;以及开放端口的情况&#xff1a; systemctl status firewalld.service(查看防火墙开启还是关闭) sudo firewall-cmd --list-all(可以查看端口开放情况) 2.使用以下命令来开启或者关闭虚拟机的防火墙 systemctl stop firewalld.ser…...

【oracle】问题分析常用查询语句

1、查看当前的数据库连接数 select count(*) from v$process ; --当前的数据库连接数2、数据库允许的最大连接数 select value from v$parameter where name processes; --数据库允许的最大连接数3、查看当前有哪些用户正在使用数据 select osuser, a.username, cpu_time/ex…...

将vue-devtools打包成edge插件

文章目录一、从github拉vue-devtools源码二、用npm安装yarn三、使用yarn安装并编译源码四、将vue-devtools打包成edge插件五、离线安装edge插件一、从github拉vue-devtools源码 目前最新的版本是v6.5.0&#xff0c;地址&#xff1a;https://github.com/vuejs/devtools 二、用n…...

SpringBoot常见面试题汇总(超详细回答)

1.什么是SpringBoot&#xff1f;Spring Boot 是一个基于 Spring 框架的开源框架&#xff0c;用于快速创建独立的、生产级别的、可运行的 Spring 应用程序。它采用了约定优于配置的理念&#xff0c;使开发者可以不需要手动配置大量的 Spring 配置文件&#xff0c;而快速搭建出符…...

上海亚商投顾:沪指窄幅震荡 ChatGPT概念再度走高

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。市场情绪沪指今日窄幅震荡&#xff0c;创业板指低开低走&#xff0c;午后跌幅扩大至1%&#xff0c;宁德时代一度跌近4%。6G概…...

【C语言进阶:指针的进阶】函数指针

本章重点内容&#xff1a; 字符指针指针数组数组指针数组传参和指针传参函数指针函数指针数组指向函数指针数组的指针回调函数指针和数组面试题的解析⚡函数指针 函数指针&#xff1a;指向函数的指针。 通过之前的学习我们知道数组指针中存放的是数组的地址&#xff0c;那么函…...

Sqoop 使用详解

Sqoop 概述Sqoop 是Apache 旗下的一款开源工具&#xff0c;用于Hadoop与关系型数据库之间传送数据&#xff0c;其核心功能有两个&#xff1a;导入数据和导出数据。导入数据是指将MySQL、Oracle等关系型数据库导入Hadoop的HDFS、Hive、HBase等数据存储系统&#xff1b;导出数据是…...

基于MATLAB开发AUTOSAR软件应用层Code mapping专题-part 1 code mapping总体介绍与Function标签页介绍

Hello,大家好,这篇文章开始我们进入一个新的专题,code mapping,即讲解AUTOSAR的元素和哪些模型元素是对应,这也是很多初学的朋友很疑惑的点,最近也有不少粉丝和朋友咨询我,说看了之前的文章基本了解了AUTOSAR有哪些元素()在数据字典的专题里我们逐个讲解过),但是就是…...

第十四节 包、权限修饰符、final、常量

包 1.同一个包下的类&#xff0c;相互可以直接访问。 2.不同包下的类要导包后才能访问。 AIT回车键导包。 权限修饰符 什么是权限修饰符? ●权限修饰符:是用来控制一个成员能够被访问的范围。 ●可以修饰成员变量&#xff0c;方法&#xff0c;构造器&#xff0c;内部类&…...

C++类和对象:初始化列表、static成员和友元

目录 一. 初始化列表 1.1 对象实例化时成员变量的创建及初始化 1.2 初始化列表 1.3 使用初始化列表和在函数体内初始化成员变量的效率比较 1.4 成员变量的初始化顺序 1.5 explicit关键字 二. static成员 2.1 static属性的成员变量 2.2 static属性的成员函数 三. 友元 …...

Windows 11 安装 Docker Desktop

Windows 环境安装 WSL2 WSL 简介 WSL 全称是 Windows Subsystem for Linux &#xff0c;适用于 Linux 的 Windows 子系统&#xff0c;可让开发人员按原样运行 GNU/Linux 环境&#xff0c;包括大多数命令行工具、实用工具和应用程序&#xff0c;且不会产生传统虚拟机或双启动设…...

设计模式-第6章(工厂模式)

工厂模式简单工厂实现工厂模式实现简单工厂 VS 工厂方法商场收银程序再再升级&#xff08;简单工厂策略装饰工厂方法&#xff09;工厂方法模式总结简单工厂实现 在简单工厂类中&#xff0c;通过不同的运算符&#xff0c;创建具体的运算类。 public class OperationFactory {pu…...

【JAVA】线程和进程

&#x1f3c6;今日学习目标&#xff1a;线程和进程 &#x1f603;创作者&#xff1a;颜颜yan_ ✨个人主页&#xff1a;颜颜yan_的个人主页 ⏰本期期数&#xff1a;第三期 &#x1f389;专栏系列&#xff1a;JAVA 线程和进程前言一、进程与线程1.进程2.线程二、线程的创建2.1 继…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...