当前位置: 首页 > 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;安装文件有点大…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...