快速排序(动图详解)(C语言数据结构)

快速排序:

        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:

        任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
        快速排序有三个版本,将一一实现。

Hoare版本:

        直接上动图理解:

当前为一遍快排。

再分别以key左右两边进行相同的排序

直到key = right = left。

综上得用递归思想。

代码如下:

void QuickSort(int* a, int begin,int end)
{if (begin >= end)//递归返回条件{return;}int right = end;int left = begin;int key = begin;while (begin < end){//找小while (begin<end && a[end]>=a[key]){end--;}//找大while (begin<end && a[begin]<=a[key]){begin++;}swap(&a[begin], &a[end]);}swap(&a[key], &a[begin]);k = begin;QuickSort(a,left,key-1);//key左边递归QuickSort(a,key+1,right);//key右边递归
}

递归展开图:

 优化代码:

        通过画递归展开图后,发现如果这个k的取值一直等于left,有缺点,递归的次数较多。

如果能改进就能让效率提高。

        改进思路:

        如果这个递归能像二叉树一样,总共只需要N*log(N)次,就只需要每次这个k取值去一个中间值,不需要去最大也不需要取最小。

        这样的改进方案,称之为三数取中。 

像刚刚,如果要递归的话一次需要递归9次,如果每次取中间的值当k,每次只需要递归3次 。

等左边递归结束式左边空间还是可以继续利用的。                 

 代码如下:

int GetMid(int* a, int begin, int end)
{int mid = (begin+end) / 2;if (a[mid] > a[end]){if (a[mid] < a[begin]){return mid;}else if (a[end] > a[begin]){return end;}elsereturn begin;}else{if (a[mid] > a[begin]){return mid;}else if (a[end] < a[begin]){return end;}elsereturn begin;}
}
void QuickSort(int* a, int begin,int end)
{if (begin >= end)//递归返回条件{return;}//三数取中int mid = GetMid(a, begin, end);swap(&a[mid], &a[begin]);int right = end;int left = begin;int key = begin;while (begin < end){//找小while (begin<end && a[end]>=a[key]){end--;}//找大while (begin<end && a[begin]<=a[key]){begin++;}swap(&a[begin], &a[end]);}swap(&a[key], &a[begin]);key = begin;QuickSort(a,left,key-1);//key左边递归QuickSort(a,key+1,right);//key右边递归
}

挖坑法版本:

        

代码如下:

void QuickSort2(int* a, int begin, int end)
{if (begin >= end)//递归返回条件{return;}//三数取中int mid = GetMid(a, begin, end);swap(&a[mid], &a[begin]);int left = begin;int right = end;int key = a[left];int hole = left;//第一个为坑while (begin < end){//找小while (begin < end && a[end] >= key){end--;}//找到小的后将数据移到刚刚坑位,并将当前位置作为坑a[hole] = a[end];hole = end;//找大while (begin < end && a[begin] <= key){begin++;}//找到大的后将数据移到刚刚坑位,并将当前位置作为坑a[hole] = a[begin];hole = begin;}a[hole] = key;QuickSort(a, left, hole - 1);//key左边递归QuickSort(a, hole + 1, right);//key右边递归
}

前后指针法:

cur找小,找到以后prev+1后交换cur和prev。

等cur == n-1之后,将a[key]和a[prev]交换,并且将key = prev。 

这个过程保证了prev和cur之间的值是大于key的。

代码如下:

void QuickSort3(int* a, int begin,int end)
{if (begin>=end)//递归返回条件{return;}//三数取中int mid = GetMid(a, begin, end);swap(&a[mid], &a[begin]);int prev = begin;int cur = prev + 1;int key = prev;while (cur<=end-begin){if (a[cur] < a[key]){prev++;if (prev < cur){swap(&a[prev],&a[cur]);}}cur++;}swap(&a[key], &a[prev]);key = prev;QuickSort(a, begin, key - 1);//key左边递归QuickSort(a, key + 1, end);//key右边递归
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/415511.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

个人怎么注册商标需要什么条件!

经常会遇到有人问普推知产老杨&#xff0c;个人怎么注册商标需要什么条件&#xff0c;首先会要有个体户执照&#xff0c;没有得先申请一个体工商户的执照才可以申请注册商标&#xff0c;再加身份证正反签字就可以&#xff0c;申请商标类别的类别与个体工商户经营范围无关&#…

APP 数据抓取 - Charles 抓包工具的使用(Charles 端口配置、CA 证书配置、Charles Android 模拟器配置)

前言说明 此文章是我在学习 Charles APP 抓包时编写&#xff0c;内容都是亲测有效&#xff0c;文章内容也有参考其他人&#xff0c;参考文章如下&#xff1a; Android 手机使用 charles 抓 https 请求&#xff08;保姆级教程&#xff09;网易 mumu 模拟器安装下载 charles 的…

redroid搭建云手机学习笔记(一)

参考链接 通过Redroid搭建自己的云手机 docker安装 docker官网目前打不开了&#xff0c;通过官网安装的方式无法实现&#xff0c;这里需要借助镜像网站来实现docker的安装 参考链接&#xff1a;https://developer.aliyun.com/mirror/docker-ce # step 1: 安装必要的一些系统…

ADB 获取屏幕坐标,并模拟滑动和点击屏幕

本文声明:本文是参考https://blog.csdn.net/beyond702/article/details/69258932编制。同时,补充了在windows系统模式下,详细的获取屏幕坐标的步骤。 1.判断设备与windows电脑USB连接是否正常 在CMD窗口输入命令:ADB devices,按ENTER键,输出如下结果,则表示连接正常。 …

【非常简单】 猿人学web第一届 第17题 天杀的 Http2.0

题目标题已经很明显了&#xff0c;Http2.0 数据接口 对应的请求协议也为 http2.0 python 代码 import httpx # pip install httpxheaders {"user-agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/128.…

LangChain学习资料

本文提供了一个LangChain框架的综合资源库&#xff0c;包括低代码工具、服务、代理、模板等&#xff0c;还列举了知识管理和聊天机器人等开源项目&#xff0c;以及学习笔记、视频教程等学习资料&#xff0c;旨在帮助开发者更好地利用和学习LangChain。 摘要由CSDN通过智能技术…

【深海王国】小学生都能玩的单片机!番外2:Arduino控制其他元器件(2)

Hi٩(๑ ^ o ^ ๑)۶, 各位深海王国的同志们&#xff0c;早上下午晚上凌晨好呀~辛勤工作的你今天也辛苦啦 (o゜▽゜)o☆ 今天大都督为大家带来单片机的新番外系列——小学生都能玩的单片机&#xff01;番外2&#xff1a;Arduino控制其他元器件&#xff0c;带你学习如何使用Ard…

【ragflow】安装2:源码安装依赖

中文文档【ragflow】安装1: docker:失败官方说的成功 docker 安装的启动失败 重新来一遍,不会重新拉取: root@k8s-master-pfsrv:/home/zhangbin/perfwork/rag# cd ragflow/ root@k8s-master-pfsrv:/home/

单片机-串口通信(二)

目录 一、串口概念 1.相关概念&#xff1a; 按数据传输方式分类&#xff1a; 按时钟分类 二、STM32F103ZET6中串口 USART特性&#xff1a; NRZ数据格式&#xff1a; 三、配置串口通信 查看硬件原理图 软件配置流程 USART相关的寄存器 新建my_usart1.c和my_usart1.h …

游戏开发者必看:Perforce龙智即将携手亮相2024 Unreal Fest上海站,打造游戏开发版本控制新生态

2024年9月5- 6日&#xff08;周四-周五&#xff09;&#xff0c;Unreal Fest Shanghai 2024将在上海宝华万豪酒店隆重举行&#xff01;作为游戏行业备受瞩目的盛会之一&#xff0c;Unreal Fest每年都会吸引来自世界各地的技术专家和行业领导者齐聚一堂&#xff0c;分享最新的技…

LabVIEW中升采样和降采样

升采样 (Upsampling) 和 降采样 (Downsampling) 是信号处理中的两种常见操作&#xff0c;用于改变信号的采样率。它们在数字信号处理&#xff08;DSP&#xff09;和许多工程应用中非常重要&#xff0c;尤其是在处理不同采样率的数据流时。 升采样 (Upsampling) 升采样是增加信…

W.A.L.T: Photorealistic Video Generation with Diffusion Models

Paper name W.A.L.T: Photorealistic Video Generation with Diffusion Models Paper Reading Note Paper URL: https://arxiv.org/pdf/2312.06662 Project URL: https://walt-video-diffusion.github.io/ TL;DR 2023 斯坦福大学和 google 联合出品的视频生成工作&#x…

ssm面向企事业单位的项目申报小程序论文源码调试讲解

2 系统实现的技术支持 2.1微信开发者工具 在传统web浏览器中&#xff0c;在加载htm15页面时先加载视图层的html和css&#xff0c;后加载逻辑层的java script&#xff0c;然后返回数据并在浏览器中展示页面。而微信开发者工具的系统层是基于Native System的&#xff0c;视图层和…

Excel 导入和导出--前后端整合

文章目录 Excel基础Easy Excel导出会员数据导入会员数据 前端代码:代码解析总结组件简介详细解释总结 用来操作excel文件的。银行网银系统导出交易明细数据、各种业务系统导出excel报表数据、批量导入业务数据。 Excel基础 **工作簿 workbook**就是一个文件工作表 sheet属于…

Linux中如何查看一个进程?如何杀死一个进程?如何查看某个端口有没有被占用?

在Linux中 如何查看一个进程&#xff1f; 使用 ps 命令 ps aux这会显示所有正在运行的进程&#xff0c;可以使用 grep 来过滤特定的进程 ps aux | grep process_name使用 top 命令 top这个命令会实时的显示系统重正在运行的进程 如何杀死一个进程&#xff1f; 使用 kill …

8、Django Admin后台中添加Logo

在项目settings.py文件 # 导入os&#xff0c;并且修改DIRS内容如下所示 import os TEMPLATES [{BACKEND: django.template.backends.django.DjangoTemplates,DIRS: [os.path.join(BASE_DIR, templates/)],APP_DIRS: True,OPTIONS: {context_processors: [django.template.con…

WebRTC协议下的视频汇聚融合技术:EasyCVR构建高效视频交互体验

视频汇聚融合技术是指将来自不同源、不同格式、不同网络环境的视频流进行集中处理、整合和展示的技术。随着视频监控、远程会议、在线教育、直播娱乐等领域的快速发展&#xff0c;视频数据的规模急剧增长&#xff0c;对视频处理能力和效率提出了更高要求。视频汇聚融合技术通过…

excel扒数据到ini文件小工具

一、源码 注释很详细&#xff0c;就不讲了 #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include <QVariant>QT_BEGIN_NAMESPACE namespace Ui { class MainWindow; } QT_END_NAMESPACEclass MainWindow : public QMainWindow {Q_OBJECTpu…

免费SSL证书申请入口——支持自动续签

SSL证书是一种数字证书&#xff0c;用于在客户端&#xff08;如浏览器&#xff09;与服务器之间建立加密通信&#xff0c;确保数据传输的安全性和完整性。它通过加密技术保护网站免受数据窃取和篡改&#xff0c;同时验证网站的身份&#xff0c;让用户确认他们正在与正确的网站进…

最全盘点!国内外主流的在线CRM有哪些?

本文将盘点10款主流的在线CRM&#xff0c;为企业选型提供参考。 在线 CRM 就如同企业与客户之间的强力纽带&#xff0c;能把企业的客户关系管理得妥妥当当。 对于企业来说&#xff0c;如果没有好用的在线 CRM&#xff0c;就像航海者失去了罗盘&#xff0c;在市场的海洋中容易迷…