排序算法:快速排序(递归)
文章目录
- 一、创始人托尼·霍尔的快速排序
- 二、挖坑法
- 三、前后指针法
所属专栏:C++初阶
引言:这里所说的快速排序有三种,第一种是霍尔大佬自创的,还有一种叫做挖坑法,另外一种叫前后指针法
一、创始人托尼·霍尔的快速排序

1.这里我们先把中间值定位数组中的首元素的值,设为key变量,大于key的放右边,小于key的放左边
2.定义left为从数组0下标开始找大于key的数,如果小于key,left就向前走一步,定义right从数组下标为n-1的位置,从右向左找小于key的数,从最右边的数开始,如果大于key,right就向后走一步
3.这里我们还要判断谁先和谁相遇(也就是谁走到相等的位置,而那个人是停止的)
如果left先走,那么left与right相遇的地方就是left走遇到right(相遇的地方的值是大于key的)
如果right先走,那么left与right相遇的地方就是right走遇到left(相遇的地方的值是小于key的)
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* p1,int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
int QuickSort(int left,int right,int* a)
{int keyi = left;int end = right;//判断谁先走的问题,我们把大于a[keyi]的放左边//小于a[keyi]的放右边,等于的话就不管//这里要判断谁先走的问题//如果left先走,那么left与right相遇的地方就是left走遇到right//如果right先走,那么left与right相遇的地方就是right走遇到leftwhile (left < right){//右边找小while(left < right && a[right] >= a[keyi])right--;//左边找大while(left < right && a[left] <= a[keyi])left++;Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);return left;
}void TestSort(int* a, int begin,int end)
{if (begin >= end)//当只有一个数时,不用排序,直接返回return;//霍尔大佬的排序int keyi = QuickSort(begin, end ,a);TestSort(a, begin,keyi-1);TestSort(a, keyi+1,end);
}
int main()
{int a[] = {6,1,2,7,9,3,4,5,10,8};TestSort(a, 0, sizeof(a) / sizeof(int) - 1);for (int i = 0; i < sizeof(a) / sizeof(int); i++)printf("%d ", a[i]);return 0;
}

这里的排序就像是二叉树的遍历,大家可以参考前面的代码
排序区间【begin,keyi-1】keyi 【keyi+1,end】(keyi为中间值,已经排好序了)
二、挖坑法
步骤如下:
1.这里的挖坑(从a[left]开始是第一个坑,然后right寻找小于key(a[left])的值,找到了这个坑就跑到a[right]去了,同时要交换一下下标hole=right)
2.然后就从left开始找大于key的值,找到了那么就是第二个坑,hole就跳到了left的位置,hole=left
3.以此类推,直到left=right的时候,此时的坑就在left=right的地方,然后a[hole]=key(此时的key就是中间值不需要排了)
int QuickSort(int left,int right,int* a)
{int key = a[left];int end = right;int hole = left;while (left < right){//右边找小while(left < right && a[right] >= key)right--;a[hole] = a[right];hole = right;//左边找大while(left < right && a[left] <key)left++;a[hole] = a[left];hole = left;}a[hole] = key;return left;
}
三、前后指针法
步骤如下:
1.首先定义一个前指针prev,和一个后指针cur
2.然后cur先向前走,如果大于key,那么继续向前走,prev,不向前走,如果小于key,那么prev和cur同时向前走(总的来说cur一直是向前走的,prev只在cur位置小于key才向前走的)
3.以此类推,直到cur>end就不走了
int QuickSort3(int left, int right, int* a)
{int key = a[left];int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] <= key && ++prev != cur)Swap(&a[prev],&a[cur]);cur++;}//最后这里的a[prev]一定是一个小于key的值,//所以需要和key这个中间值换一下,以达到key已经排好序Swap(&a[prev], &a[left]);return prev;
}

相关文章:
排序算法:快速排序(递归)
文章目录 一、创始人托尼霍尔的快速排序二、挖坑法三、前后指针法 所属专栏:C初阶 引言:这里所说的快速排序有三种,第一种是霍尔大佬自创的,还有一种叫做挖坑法,另外一种叫前后指针法 一、创始人托尼霍尔的快速排序 1.这里我们先…...
蓝桥杯每日一题(BFS)
1562 微博转发 开始思路错误点:在用拉链法保存关注信息的时候,因为要看一个用户发的有多少转发的,所以要以用户为坑位,所有关注这个坑位的用户为链表。(开始弄反了) e数组存某个用户的idx,ne是…...
【C语言】linux内核pci_save_state
一、中文注释 //include\linux\pci.h /* 电源管理相关的例程 */ int pci_save_state(struct pci_dev *dev);//drivers\pci\pci.c /*** pci_save_state - 在挂起前保存PCI设备的配置空间* dev: - 我们正在处理的PCI设备*/ int pci_save_state(struct pci_dev *dev) {int i;/* X…...
轻松打造完美原型:9款在线工具推荐
早年,UI设计师选择的工具有限,功能相对单一,大多数在线原型设计工具都是国外的,语言和网络都增加了设计工作的负担。如今,国内外有许多在线原型设计工具,不仅可以在浏览器上使用,而且还具有团队…...
Vue3中Pinia状态管理库学习笔记
pinia的基本使用 <template><div><h2>Home View</h2> <h2>count:{{ counterStore.count }}</h2><h2>count:{{ count }}</h2><button click"increment">count1</button></div> </template>…...
共谋企业出海新篇章纷享销客荣获数字中国企业峰会“卓越成果奖”
3月9日,2024数字中国企业峰会在杭州西湖中维香溢大酒店成功举办,众多数字化领域专家、知名企业 CIO 代表到场。峰会旨在推动数字化转型与创新发展,为企业出海和国际合作搭建交流与合作的平台。本次峰会的颁奖环节,纷享销客凭借其卓…...
【MySQL】group_concat 函数和 locate 函数运用之找到每篇文章的主题
力扣题 1、题目地址 2199. 找到每篇文章的主题 2、模拟表 表:Keywords Column NameTypetopic_idintwordvarchar (topic_id, word) 是该表的主键(具有唯一值的列的组合)。该表的每一行都包含一个主题的 id 和一个用于表达该主题的词。可…...
RedisCluster集群中的插槽为什么是16384个?
RedisCluster集群中的插槽为什么是16384个? CRC16的算法原理。 1.根据CRC16的标准选择初值CRCIn的值2.将数据的第一个字节与CRCIn高8位异或3.判断最高位,若该位为0左移一位,若为1左移一位再与多项式Hex码异或4.重复3至9位全部移位计算结束5…...
一直出现问题,发现服务器磁盘空间已满导致,腾出服务器磁盘空间命令
要解决服务器磁盘空间已满的问题,你可以按照以下步骤操作: 查看磁盘使用情况:使用df -h, du -s -h ./*命令来查看服务器的磁盘空间使用情况。查找大文件:使用du -a | sort -rn | head -5命令来找出占用空间最大的前5个…...
吴恩达机器学习笔记 二十三 倾斜数据集的误差指标 精确率 召回率 精确率与召回率的平衡 F1分数
如果数据集的正例和反例的比例非常倾斜,常用的错误指标如 准确率(accuracy) 并不好用。此时可以用精确率和召回率。 精确率(precision):真阳的样本数/预测为阳的样本数真阳数/(真阳假阳) 召回率(recall):…...
无人游艇的研发和开发对于多个领域具有重要
无人游艇的研发和开发对于多个领域具有重要性。 首先,无人游艇可以在海上进行各种任务,如海洋科学研究、资源勘探和监测、海洋环境保护等。相比传统的人工操作船只,无人游艇可以长时间在海上工作,可以自动化执行任务,…...
在AI创业热潮下,如何抓住AI赚钱机会,实现人生逆袭
随着人工智能技术的迅猛发展,AI创业热潮正席卷全球。这不仅为科技领域的专业人士提供了无限的商机,也为普通人开辟了全新的赚钱途径。本文将为您揭示在AI创业热潮下,普通人如何抓住AI赚钱机会,实现人生逆袭,同时探讨哪些行业适合应用AI技术。 一、普通人如何抓住AI赚钱机…...
JETSON 配置并跑通 NanoDet
JETSON 配置 NanoDet 文章目录 JETSON 配置 NanoDetNanoDet 介绍源码环境搭建及测试配置 NanoDet 的环境环境配置过程中遇到的问题:环境配置完毕验证 NanoDet NanoDet 介绍 可以参考这个博客:NanoDet:这是个小于4M超轻量目标检测模型 源码 …...
突破编程_C++_C++11新特性(unordered_multimap)
1 概述 std::unordered_multimap 是一个哈希表实现的无序容器,它存储的元素是键值对,并且允许键的重复。这意味着同一个键可以关联多个值。在 std::unordered_multimap 中,元素的插入顺序是不确定的,并且不会因为元素的插入、删除…...
15.WEB渗透测试--Kali Linux(三)
免责声明:内容仅供学习参考,请合法利用知识,禁止进行违法犯罪活动! 内容参考于: 易锦网校会员专享课 上一个内容:14.WEB渗透测试--Kali Linux(二)-CSDN博客 Kali工具使用 3389远…...
Android-Framework pm list packages和pm install返回指定应用信息
一、环境 高通 Android 13 注:Android10 和Android13有些差异,代码位置不变,参照修改即可 二、pm简单介绍 pm工具为包管理(package manager)的简称 可以使用pm工具来执行应用的安装和查询应用宝的信息、系统权限、…...
CSS
什么是CSS? CSS是一门语言,用于控制网页表现 CSS(Cascading Style Sheet):层叠样式表 W3C标准:网页主要由三部分组成 结构:HTML表现:CSS行为:JavaScript CSS导入方式…...
算法详解——选择排序和冒泡排序
一、选择排序 选择排序算法的执行过程是这样的:首先,算法遍历整个列表以确定最小的元素,接着,这个最小的元素被置换到列表的开头,确保它被放置在其应有的有序位置上。接下来,从列表的第二个元素开始&#x…...
图论(蓝桥杯 C++ 题目 代码 注解)
目录 迪杰斯特拉模板(用来求一个点出发到其它点的最短距离): 克鲁斯卡尔模板(用来求最小生成树): 题目一(蓝桥王国): 题目二(随机数据下的最短路径&#…...
矩阵起源新一年喜报连连!
新春伊始 矩阵起源向大家分享 一连串好消息 首先,公司创始人兼CEO王龙先生获评“2023深圳创新突出贡献人物“。这一荣誉是对其在推动数据库行业技术创新和产品开发方面所做出的卓越贡献的认可。他的领导力和创新精神不仅引领我司取得了显著的成就,也为…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...


