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

详解基于快速排序算法的qsort的模拟实现

目录

1. 快速排序

1.1 快速排序理论分析 

1.2 快速排序的模拟实现 

2. qsort的模拟实现 

2.1 qsort的理论分析

2.2 qsort的模拟实现


qsort函数是基于快速排序思想设计的可以针对任意数据类型的c语言函数。要对qsort进行模拟实现,首先就要理解快速排序。

1. 快速排序

1.1 快速排序理论分析 

上一期博客选择排序,冒泡排序,插入排序,快速排序及其优化-CSDN博客我们大概讲解了快速排序的思路,现在我们来详细讲解以下快速排序。

 让我们来逐帧分析快速排序的思想。

1. 第一步便是找到基准数,开始分区:基准数可以选择第一个,最后一个,也可以是随机的(为了便于理解,以下的图都默认选的是第一个,当然代码是随机的,重要的是先把交换三个数的本质理解到)

2.  分而治之,调整后基准数的左右两边,再进行相同的操作,直到不能再排序(数组长度为1时,就不能再排序了)

 

1.2 快速排序的模拟实现 

以上便是对快速排序底层逻辑的分析, 接下来以c语言为例,讲解模拟实现快速排序。

1. 选一个基准数,这里选的是首元素

2. 开始分区,遍历整个数组,开始交换位置(三个数),小的在前,大的在后

3. 开始递归,左右两边都要开始递归,由于需要知道边界,所以分区时,应该再返回基准数的地址。同时为了避免递归递而不归,应设置最小的长度


/*返回值:基准数最后的下标参数:需要分区的部分(从头到尾开始排)
*/
int partition(int arr[], int start, int end)
{int len = end - start;int* ppivot = arr + start;int* s = ppivot + 1;while (len--){if (*ppivot >= *s){int temp = *s;*s = *(ppivot + 1);*(ppivot + 1) = *ppivot;*ppivot = temp;ppivot++;}s++;}return ppivot - arr;
}/*返回值:arr首元素的地址参数:需要排序的部分(从头到尾)
*/int* quick_sort(int arr[], int start, int end)
{assert(arr);int* p = arr;if (end > start){int pivot = partition(arr, start, end);quick_sort(arr, start, pivot - 1);quick_sort(arr, pivot + 1, end);}return p;
}

 当然,对于分区的排序可以进行优化,使用双指针也可以。双指针就是首尾往中间交换的模式,效率自然更高。这里不过多展开去讲。

2. qsort的模拟实现 

2.1 qsort的理论分析

C 库函数 void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)) 对数组进行排序。它可以接收任意类型进行排序,其实跟快速排序接收int类型差不多,只是这里多了一个强制类型转换。

2.2 qsort的模拟实现

qsort的模拟实现,基本就是在quick_sort上做改造,将原来只可以进行int数据类型的改成任意数据类型。

1. 原来是数值之间的比较,现在要改成有专门的比较数据大小的函数(字符:strcmp)

2. 交换位置,原来int直接就可以交换数据,现在强制类型转换成char*后,单位转换的变少了,则需要循环4次,才够int 四个字节

3. 指针加1, 原来有确定类型,现在是void* 原来加1,现在就应该加size

int cmp_int(const void* a, const void* b)
{return *(int*)a - *(int*)b;
}/*返回值:基准数最后的下标参数:需要分区的部分(从头到尾开始排)
*/
int partition(void* arr, int start, int end, size_t size)
{int len = end - start;char* ppivot = ((char*)arr + start * size);char* s = ppivot + size;while (len--){if ((*cmp_int)(ppivot, s) > 0){for (int i = 0; i < size; i++){int temp = *(s+i);*(s+i) = *(ppivot + size + i);*(ppivot + size + i) = *(ppivot+i);*(ppivot+i) = temp;}ppivot += size;}s += size;}return (int)((ppivot - (char*)arr) / size);
}/*返回值:arr首元素的地址参数:需要排序的部分(从头到尾)
*/void* quick_sort(void* arr, int start, int end,size_t size)
{assert(arr);if (end > start){int pivot = partition(arr, start, end,size);quick_sort(arr, start, pivot - 1,size);quick_sort(arr, pivot + 1, end,size);}return arr;
}void* my_qsort(void* arr, size_t len, size_t size, int (*cmp_int)(const void* a, const void* b))
{assert(arr);int start = 0;int end = (int)len - 1;quick_sort(arr, start, end, size);return arr;
}

感谢各位大佬的支持与指正!!!

相关文章:

详解基于快速排序算法的qsort的模拟实现

目录 1. 快速排序 1.1 快速排序理论分析 1.2 快速排序的模拟实现 2. qsort的模拟实现 2.1 qsort的理论分析 2.2 qsort的模拟实现 qsort函数是基于快速排序思想设计的可以针对任意数据类型的c语言函数。要对qsort进行模拟实现&#xff0c;首先就要理解快速排序。 1. 快…...

鸿蒙Harmony应用开发—ArkTS声明式开发(绘制组件:Polyline)

折线绘制组件。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 无 接口 Polyline(value?: {width?: string | number, height?: string | number}) 从API version 9开始&#xff0c…...

项目风险管理

项目风险管理 1 规划风险管理2 识别风险1.2 输出 3 实施定性风险分析3.1 输入3.2 输出 4 实施定量风险分析4.1 输入4.2 输出 5 规划风险应对5.1 输入5.2 输出 6 实施风俗应对6.1 输入6.2 输出 7 监督风险7.1 输入7.2 输出 项目风险是一种不确定的事件或条件&#xff0c;一旦发生…...

glib交叉编译

Glib交叉编译 逸一时&#xff0c;误一世。 —— 田所浩二「夏夜银梦」 交叉编译 GLib 涉及到在一个平台上生成能够在另一个平台上运行的目标文件。在这种情况下&#xff0c;我们将会在一台主机&#xff08;通常是开发机器&#xff09;上使用交叉编译工具链来构建 GLib 库&#…...

Android11实现能同时开多个录屏应用(或者共享屏幕或投屏时录屏)

1.概述 Android原生对MediaProjection的管理逻辑&#xff0c;是如果服务端已经保存有MediaProjection的实例&#xff0c;那么再次创建的时候&#xff0c;之前的MediaProjection实例就会被暂停&#xff0c;并且引用指向新的实例&#xff0c;也就导致了当开启后一个录屏应用时&a…...

音视频实战---音频重采样

1、使用swr_alloc()创建重采样实例 2、使用av_opt_set_int函数设置重采样输入输出参数 3、使用swr_init函数初始化重采样器 4、使用av_get_channel_layout_nb_channels函数计算输入源的通道数 5、给输入源分配内存空间–av_samples_alloc_array_and_samples 6、计算输出采…...

主存中存储单元地址的分配

主存中存储单元地址的分配 为什么写这篇文章? 因为我看书中这部分时&#xff0c;看到下面的计算一下子没反应过来&#xff1a; 知识回顾&#xff08;第1章&#xff09; 计算机系统中&#xff0c;字节是最小的可寻址的存储单位&#xff0c;通常由8个比特&#xff08;bit&…...

Python和R的区别是什么,Python与R的应用场景是什么?

如果你这么问&#xff0c;那么你可能正站在数据科学的起点。对于志在成为数据专业人员的你来说&#xff0c;学习编程是无疑的。我想行你早就听过Python 与R的比较之声&#xff0c;并在选择中感到困惑。在此&#xff0c;我想说&#xff0c;也算是一种安慰吧&#xff1a;对于语言…...

azure databricks 常用的JDBC连接

做个笔记常用的spark-jdbc连接 1、mysql 的连接 def query_mysql(database,sqlstr):jdbcUsernamejdbcHostname " "jdbcDatabase ""jdbcPort 3306mysql_df spark.read \.format("jdbc") \.option("driver","com.mysql.cj.jdb…...

功能齐全的免费 IDE Visual Studio 2022 社区版

面向学生、开放源代码和单个开发人员的功能齐全的免费 IDE 下载地址 Visual Studio 2022 社区版 - 下载最新的免费版本 Visual Studio 2022 Community Edition – Download Latest Free Version 准备安装 选择需要安装的程序 安装进行中 使用C学习程序设计相关知识并培养编程…...

FreeRTOS入门基础

RTOS是为了更好地在嵌入式系统上实现多任务处理和时间敏感任务而设计的系统。它能确保任务在指定或预期的时间内得到处理。FreeRTOS是一款免费开源的RTOS&#xff0c;它广泛用于需要小型、预测性强、灵活系统的嵌入式设备。 创建第一个任务 任务函数&#xff1a;任务是通过函数…...

蓝桥杯-24点-搜索

题目 思路 --暴力递归全组合的方法。只有4个数&#xff0c;4种计算方式&#xff0c;共有4 * 3 * 2 * 1 * 4种不同的情况&#xff0c;可以写递归来实现。 --每次计算都是两个数之间的运算&#xff0c;因此4个数需要3次计算&#xff0c;第一次计算前有4个数&#xff0c;第二次有…...

【附下载】3Ds Max从安装、配置到入门提高和高级用法

#3Ds Max 一、安装 1.1 安装说明 地址&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1lwKMbgbE32wCL6PpMv706A?pwddll8 提取码&#xff1a;dll8 –来自百度网盘超级会员V2的分享 安装说明&#xff1a;文件夹里有安装说明 安装解压即可 关键就是将crack文件放到自己…...

开源堡垒机Jumpserver

开源堡垒机Jumpserver 文章目录 开源堡垒机Jumpserver1 Jumpserver介绍2 Jumpserver部署用户管理资产创建账号管理模板添加 用户组管理权限管理远程连接免密连接 1 Jumpserver介绍 Jumpserver 是全球首款完全开源的堡垒机&#xff0c;使用 GNU GPL v2.0 开源协议&#xff0c;是…...

PyTorch学习笔记之基础函数篇(十五)

文章目录 数值比较运算8.1 torch.equal()函数8.2 torch.ge()函数8.3 torch.gt()函数8.4 torch.le()函数8.5 torch.lt()函数8.6 torch.ne()函数8.7 torch.sort()函数8.8 torch.topk()函数 数值比较运算 8.1 torch.equal()函数 torch.equal(tensor1, tensor2) -> bool这个函…...

Latex插入pdf图片,去除空白部分

目录 参考链接&#xff1a; 流程&#xff1a; 参考链接&#xff1a; ​科研锦囊之Latex-如何插入图片、表格、参考文献 http://t.csdnimg.cn/vpSJ3 流程&#xff1a; Latex的图片插入支持PDF文件&#xff0c;这里笔者建议都使用PDF文件进行图片的插入&#xff0c;因为PDF作…...

微服务:高并发带来的问题的容错方案

1.相关脚本&#xff08;陈天狼&#xff09; 启动nacos客户端&#xff1a; startup.cmd -m standalone 启动sentinel控制台&#xff1a; # 直接使⽤jar命令启动项⽬(控制台本身是⼀个SpringBoot项⽬) java -Dserver.port8080 -Dcsp.sentinel.dashboard.serverlocalhost:808…...

sqllab第35-45关通关笔记

35关知识点&#xff1a; 宽字节注入数值型注入错误注入 payload:id1andextractvalue(1,concat(0x7e,database(),0x7e))0--联合注入 payload:id0unionselect1,database(),version()-- 36关知识点&#xff1a; 字符型注入宽字节注入错误注入 payload:id1%df%27andextractvalue(…...

Jenkins流水线将制品发布到Nexus存储库

1、安装jenkins&#xff08;建议别用docker安装&#xff0c;坑太多&#xff09; docker run -d -p 8089:8080 -p 10241:50000 -v /var/jenkins_workspace:/var/jenkins_home -v /etc/localtime:/etc/localtime --name my_jenkins --userroot jenkins/jenkins:2.449 坑1 打开x…...

信息学奥赛一本通之MAC端VSCode C++环境配置

前提 安装 Visual Studio CodeVSCode 中安装 C/C扩展确保 Clang 已经安装&#xff08;在终端中输入命令&#xff1a;clang --version 来确认是否安装&#xff09;未安装&#xff0c;在命令行执行xcode-select --install 命令&#xff0c;会自行安装&#xff0c;安装文件有点大…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...

嵌入式面试常问问题

以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...

统计学(第8版)——统计抽样学习笔记(考试用)

一、统计抽样的核心内容与问题 研究内容 从总体中科学抽取样本的方法利用样本数据推断总体特征&#xff08;均值、比率、总量&#xff09;控制抽样误差与非抽样误差 解决的核心问题 在成本约束下&#xff0c;用少量样本准确推断总体特征量化估计结果的可靠性&#xff08;置…...