当前位置: 首页 > 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;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

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

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

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...