【C/C++ 05】快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序算法,其基本思想是:任取待排序序列中的某元素作为基准值,按照该基准值将待排序集合分割成两个子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后左右子序列递归该过程,直到所有元素都排列在相应的位置上为止。

  • 排序对象:数组、链表
  • 时间复杂度:O(n * \log n)
  • 空间复杂度:O(1)
  • 是否稳定:否
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{if(right - left <= 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div = partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div+1, right)QuickSort(array, div+1, right);
}

上述为快速排序算法递归实现的主框架,与二叉树前序遍历的规则类似。

快速排序算法可以由多种实现方法,如霍尔法、挖坑法、前后指针法,目前最优的算法是前后指针法,其基本思路是:

  1. 选择数组中的一个元素作为枢轴(一般是第一个元素),其元素为关键值key,而key值最好是数组的中位数(仅在前中后三个元素中取中位数)
  2. 将数组划分为两个子数组,左子数组的元素都小于等于枢轴元素,右子数组的元素都大于等于枢轴元素
  3. 对这两个子数组分别递归调用快速排序算法,继续进行划分和排序
  4. 递归的结束条件是子数组的长度为1或0,即已经有序或为空数组,不需要再进行排序
  5. 通过不断划分和排序,最终实现整体的排序
  6. 在划分过程中,通过比价元素与枢轴元素的大小关系,将元素划分到对应的区域

// 数组开始、中间、结尾三个元素找到中位数,将其作为key值并返回下标
int MidIndex(int* arr, int l, int m, int r)
{if (arr[l] < arr[r]){if (arr[m] < arr[l])return l;else if (arr[m] > arr[r])return r;elsereturn m;}else{if (arr[m] > arr[l])return l;else if (arr[m] < arr[r])return r;elsereturn m;}
}// 前后指针法(快慢指针法)
// 快排每一次递归的核心就是PtrPtr算法返回新的关键字key的下标
// 每一次PtrPtr算法就是为了将小于key的数移到key的左边,将大于key的数移到key的右边
// 当多次进行递归后,数组的有序度已经很高了,所以此时也可以不再递归而是采用直接插入排序
int PtrPtr(int* arr, int begin, int end)
{if (begin >= end)return;int slow = begin;int fast = slow + 1;while (fast <= end){if (arr[fast] < arr[begin] && ++slow != fast)Swap(&arr[slow], &arr[fast]);fast++;}Swap(&arr[begin], &arr[slow]);return slow;	// 返回新的key值下标
}void QuickSort(int* arr, int begin, int end)
{if (begin >= end)return;int mid = (begin + end) / 2;int iKey = MidIndex(arr, begin, mid, end);Swap(&arr[begin], &arr[iKey]);iKey = PtrPtr(arr, begin, end);QuickSort(arr, begin, iKey - 1);QuickSort(arr, iKey + 1, end);
}

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

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

相关文章

uniapp H5 实现上拉刷新 以及 下拉加载

uniapp H5 实现上拉刷新 以及 下拉加载 1. 先上图 下拉加载 2. 上代码 <script>import DragableList from "/components/dragable-list/dragable-list.vue";import {FridApi} from /api/warn.jsexport default {data() {return {tableList: [],loadingHi…

路由反射器 RR 配置实验

一、预习&#xff1a; RR&#xff1a;Route Reflect&#xff0c;是为了解决 IBGP 水平分割问题&#xff0c;即&#xff1a;【BGP 路由器从 IBGP 收到的路由&#xff0c;不会传递给其他 IBGP 邻居】&#xff0c;因此需要使用路由反射器&#xff0c;这样&#xff0c;未收到路由的…

【Java反序列化】Shiro-550漏洞分析笔记

目录 前言 一、漏洞原理 二、Shiro环境搭建 三、Shiro-550漏洞分析 解密分析 加密分析 四、URLDNS 链 前言 shiro-550反序列化漏洞大约在2016年就被披露了&#xff0c;在上学时期也分析过&#xff0c;最近在学CC链时有用到这个漏洞&#xff0c;重新分析下并做个笔记&…

260:vue+openlayers 通过webgl方式加载矢量图层

第260个 点击查看专栏目录 本示例介绍如何在vue+openlayers中通过webgl方式加载矢量图层。在做这个示例的时候,采用vite的方式而非webpack的方式。这里的基础设置需要改变一下。 ol的版本7.5.2或者更高。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果 文…

如何使用docker compose安装APITable并远程访问登录界面

文章目录 前言1. 部署APITable2. cpolar的安装和注册3. 配置APITable公网访问地址4. 固定APITable公网地址 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 人工智能学习网站&#xff0c; 通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。 …

【虚拟机数据恢复】异常断电导致虚拟机无法启动的数据恢复案例

虚拟机数据恢复环境&#xff1a; 某品牌R710服务器MD3200存储&#xff0c;上层是ESXI虚拟机和虚拟机文件&#xff0c;虚拟机中存放有SQL Server数据库。 虚拟机故障&#xff1a; 机房非正常断电导致虚拟机无法启动。服务器管理员检查后发现虚拟机配置文件丢失&#xff0c;所幸…

idea 打包跳过测试

IDEA操作 点击蓝色的小球 手动命令 mvn clean package -Dmaven.test.skiptrue# 下载源码![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/ff15aad1c9a546b6ab0556b5b135f409.png)

Linux:重定向

Linux&#xff1a;重定向 输出重定向追加重定向输出重定向与追加重定向的本质输入重定向 输出重定向 在Linux中&#xff0c;输出重定向是一种将命令的输出发送到不同位置的方法。通常&#xff0c;执行命令时&#xff0c;输出会显示在终端上。然而&#xff0c;使用输出重定向&a…

C语言菜鸟入门·判断语句(if语句、if...else语句、嵌套if语句)详细介绍

目录 1. if语句 2. if...else语句 3. if...else if...else 语句 4. 嵌套if语句 C 语言把任何非零和非空的值假定为 true&#xff0c;把零或 null 假定为 false。 语句描述if语句一个 if 语句 由一个布尔表达式后跟一个或多个语句组成。if...else语句一个 if 语句 后可跟…

HDFS Federation前世今生

一 背景 熟悉大数据的人应该都知道&#xff0c;HDFS 是一个分布式文件系统&#xff0c;它是基于谷歌的GFS实现的开源系统&#xff0c;设计目的就是提供一个高度容错性和高吞吐量的海量数据存储解决方案。在经典的HDFS架构中有2个NameNode和多个DataNode&#xff0c;如下 从上面…

etcd技术解析:构建高可用分布式系统的利器

1. 引言 随着云原生技术的兴起&#xff0c;分布式系统的构建变得愈发重要。etcd作为一个高可用的分布式键值存储系统&#xff0c;在这个领域发挥着至关重要的作用。本文将深入探讨etcd的技术细节&#xff0c;以及如何利用它构建高可用的分布式系统。 2. etcd简介 etcd是一个开…

力扣238. 除自身以外数组的乘积(前后缀和)

Problem: 238. 除自身以外数组的乘积 文章目录 题目描述思路复杂度Code 题目描述 思路 思路1&#xff1a; 1.先求取数组的包括当前下标值得前后缀乘积&#xff08;利用两个数组记录下来分别为leftProduct和rightProduct&#xff09; 2.当求取一个下标为i的数组中的元素&#x…

2024年阿里云幻兽帕鲁Palworld游戏服务器优惠价格表

自建幻兽帕鲁服务器租用价格表&#xff0c;2024阿里云推出专属幻兽帕鲁Palworld游戏优惠服务器&#xff0c;配置分为4核16G和4核32G服务器&#xff0c;4核16G配置32.25元/1个月、10M带宽66.30元/1个月、4核32G配置113.24元/1个月&#xff0c;4核32G配置3个月339.72元。ECS云服务…

msvcr120.dll丢失的三种解决办法,分享详细解决教程

msvcr120.dll文件丢失有这三种方法可以解决&#xff0c;学会这三种方法的任何一种&#xff0c;以后再出现dll文件丢失的情况都能很好地解决&#xff0c;第一种方法最为简单。先给大家说说msvcr120.dll文件为什么会丢失&#xff1f;丢失的原因是什么&#xff1f; 一.msvcr120.d…

如何获得《幻兽帕鲁》隐藏帕鲁唤夜兽?13000个配种配方查询 幻兽帕鲁Steam好评率还在涨 Mac苹果电脑玩幻兽帕鲁 Crossover玩Windows游戏

《幻兽帕鲁》是一款Steam平台热门游戏&#xff0c;开放式大陆和养成式冒险结合&#xff0c;成为2024首款热门游戏&#xff0c;不过由于官方仅发布了Windows版的游戏客户端&#xff0c;Mac用户无法直接玩&#xff0c;好在有Crossover这样的神器&#xff0c;让苹果电脑也能玩上《…

Mov转MP4怎么转换?如何播放mov视频?

MOV文件格式的使用场景 MOV文件格式以其支持多种媒体数据类型的特性而闻名&#xff0c;包括视频、音频、文本、动画等。它常用于存储包含视频剪辑、电影、音频轨道等多媒体元素的文件。由于其在质量和编辑方面的优越性&#xff0c;MOV文件在电影制作、广告宣传、多媒体演示等领…

RabbitMQ简单模式和工作模式

RabbitMQ 是一个消息队列中间件&#xff0c;用于在分布式系统中进行消息传递。在 RabbitMQ 中&#xff0c;有几种工作模式&#xff0c;其中简单模式和工作模式是其中两种基本的模式之一。 简单模式&#xff08;Simple Mode&#xff09;&#xff1a; 在简单模式中&#xff0c;有…

docker-学习-1

docker-学习-第一天 docker-学习-第一天1.docker是什么&#xff1f;容器的好处docker现况理解docker 2.在centos7中安装docker2.1安装步骤 3.docker里边三个非常重要的概念3.1安装一个阿里云的国内的镜像加速器&#xff0c;可以到阿里云上下载镜像了 4.docker的命令4.1 docker …

最优化基础 - (最优化问题分类、凸集)

系统学习最优化理论 什么是最优化问题&#xff1f; 决策问题&#xff1a; &#xff08;1&#xff09;决策变量 &#xff08;2&#xff09;目标函数&#xff08;一个或多个&#xff09; &#xff08;3&#xff09;一个可由可行策略组成的集合&#xff08;等式约束或者不等式约束…

Python根据Excel表进行文件重命名

一、问题背景 在日常办公过程中&#xff0c;批量重命名是经常使用的操作。之前我们已经进行了初步探索&#xff0c;主要是通过批处理文件、renamer软件或者Python中的pathlib等模块对当前目录下的文件进行批量重命名。 而今天我们要使用的是PythonExcel的方法对指定目录下的文…