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

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学

一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件&#xff0c;其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时&#xff0c;价带电子受激发跃迁至导带&#xff0c;形成电子-空穴对&#xff0c;导致材料电导率显著提升。…...

Python的__call__ 方法

在 Python 中&#xff0c;__call__ 是一个特殊的魔术方法&#xff08;magic method&#xff09;&#xff0c;它允许一个类的实例像函数一样被调用。当你在一个对象后面加上 () 并执行时&#xff08;例如 obj()&#xff09;&#xff0c;Python 会自动调用该对象的 __call__ 方法…...