排序算法:快速排序(递归)

文章目录

    • 一、创始人托尼·霍尔的快速排序
    • 二、挖坑法
    • 三、前后指针法

在这里插入图片描述
所属专栏: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走遇到left
	while (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;
}

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

AI跟踪报道第33期-新加坡内哥谈技术-AI新闻快报:GTC和终结GPU/TPU的热力学未来Chip?

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

【gpt实践】比OpenAI 的 GPT-4 更好模型 Claude 3.0

Google 最近发布了最新的 Gemini 1.5 语言模型&#xff0c;震惊了世界。这是目前功能最强大的模型&#xff0c;拥有 100 万个上下文窗口&#xff0c;是所有大型基础模型中最大的。 OpenAI 的 GPT-4 才具有 128K 上下文窗口。 最近&#xff0c;谷歌最接近的竞争对手之一 Anthro…

【算法】AC自动机的优化:增量更新与删除

一、概述 AC自动机&#xff08;Aho-Corasick Automation&#xff09;是著名的多模匹配算法&#xff0c;源于贝尔实验室&#xff0c;并且在实际应用中得到广泛的引用&#xff0c;且具有以下特点&#xff1a; 只需要扫描一次文本&#xff0c;即可获取所有匹配该文本的模式串复杂…

svg代码应用于button

将svg代码的path属性应用于按钮内容&#xff0c;去掉按钮边框&#xff0c;并且自适应svg大小&#xff0c;以下实现的是一个旋转按钮。 svg代码如下(iconfont下载)&#xff1a; <svg t"1710741485848" class"icon" viewBox"0 0 1024 1024" ve…

SpringCloudLoadBalancer入门与实战系列

目录 一、什么是LoadBalancer&#xff1f; 1.1 负载均衡的分类 1.2 负载均衡策略 二、 为什么要学习 Spring Cloud Balancer &#xff1f; 三、 Spring Cloud LoadBalancer 内置的两种负载均衡策略 3.1 轮询负载均衡策略&#xff08;默认的&#xff09; 3.2 随机负载均衡…

高防服务器秒解是什么意思

高防服务器秒解是指高防服务器在遭受大规模的DDoS攻击时&#xff0c;能够迅速解决问题或应对攻击。DDoS攻击是指攻击者通过向目标服务器发送大量的请求&#xff0c;使服务器资源耗尽或无法正常响应其他合法用户的请求&#xff0c;从而导致服务不可用。高防服务器通过具备高性能…

C++容器适配器与stack,queue,priority_queue(优先级队列)的实现以及仿函数(函数对象)与deque的简单介绍

&#x1f389;个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名乐于分享在学习道路上收获的大二在校生 &#x1f648;个人主页&#x1f389;&#xff1a;GOTXX &#x1f43c;个人WeChat&#xff1a;ILXOXVJE &#x1f43c;本文由GOTXX原创&#xff0c;首发CSDN&…

centos云服务器安装cs(cobaltstrike4.0)教程

1、先安装JAVA环境 mkdir download #创建download目录 cd download #进入download目录 mkdir java1.8 #在download目录下再创建java1.8目录 cd java1.8 #进入java1.8目录 wget https://repo.huaweicloud.com/java/jdk/8u201-b09/jdk-8u201-linux-x64.tar.gz #下载jdk压缩包 tar…

积分法卷径计算(CODESYS ST完整源代码)

在学习积分法卷径计算课程之前大家需要属性下PLC的数值积分器运算。 1、博途PLC积分法卷径计算完整源代码 https://rxxw-control.blog.csdn.net/article/details/136719982https://rxxw-control.blog.csdn.net/article/details/1367199822、转动圈数累积功能块 https://rxxw…

代码随想录算法训练营三刷day27 | 回溯之 39. 组合总和 40.组合总和II 131.分割回文串

三刷day27 39. 组合总和回溯三部曲剪枝优化 40.组合总和II回溯三部曲 131.分割回文串回溯三部曲判断回文子串 39. 组合总和 题目链接 解题思路&#xff1a; 本题没有数量要求&#xff0c;可以无限重复&#xff0c;但是有总和的限制&#xff0c;所以间接的也是有个数的限制。 本…

组件化开发

一、引言 Vue.js 的组件化开发是其核心特性之一&#xff0c;它允许开发者将复杂的界面拆分为可复用的、独立的、小的组件&#xff0c;从而提高开发效率和代码的可维护性。 二、关键点 1.组件的定义 在components下创建.vue文件timecard.vue用来编辑内容。 文件创建完毕后&am…

我的导航学习笔记仓库大改版,欢迎关注!!

链接&#xff1a;https://github.com/LiZhengXiao99/Navigation-Learning 我的导航学习笔记&#xff0c;内容涵盖导航定位开源程序的源码解读 ( 包括&#xff1a;RTKLIB、GAMP、SoftGNSS、KF-GINS、ORB-SLAM3 等)、各种导航设备的使用方式、书籍讲义、博客翻译、开源项目梳理、…

python爬取微博话题、关键词下方的所有帖子

文章目录 github repository项目介绍输出安装必备库获取cookiegithub repository 网址:https://github.com/dataabc/weibo-search 在GitHub获取到的非常成熟的微博话题、关键词等微博帖子的获取方案,并且可以指定一个或多个关键词,指定获取微博类型,指定获取日期等等。 项…

文件处理(二)

CSV文件的读取和写入 CSV文件的操作 csv是逗号分隔符文本格式&#xff0c;常用于数据交换、Excel文件和数据库数据的导入和导出。 与Excel文件不同&#xff0c;CSV文件中&#xff1a; 值没有类型&#xff0c;所有值都是字符串不能指定字体颜色等样式不能指定单元格的宽高&…

全网最全100个AI工具导航网站合集

随着ChatGPT年前的爆火&#xff0c;人工智能也变成当今最热门的领域之一&#xff0c;它正在改变着我们的生活和工作方式。无论你是想要学习人工智能的基础知识&#xff0c;还是想要利用人工智能来提升你的业务效率和创新能力&#xff0c;都需要找到合适的AI工具来帮助你实现目标…

VS Code安装Live Server插件搭建web网页结合内网穿透实现公网访问

文章目录 前言1. 编写MENJA小游戏2. 安装cpolar内网穿透3. 配置MENJA小游戏公网访问地址4. 实现公网访问MENJA小游戏5. 固定MENJA小游戏公网地址 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&…

数仓建模简介

1 建模的意义 如果把数据看作图书馆里的书&#xff0c;我们希望看到它们在书架上分门别类地放置&#xff1b;如果把数据看作城市的建筑&#xff0c;我们希望城市规划布局合理&#xff1b;如果把数据看作电脑文件和文件夹&#xff0c;我们希望按照自己的习惯有很好的文件夹组织方…

docker小白第十二天

docker小白第十二天 docker network简介 docker不启动时默认的网络情况。 # 停止docker服务 systemctl stop docker.socket systemctl stop docker # 查看docker镜像 docker images输入查看docker镜像命令后&#xff0c;显示未连接到docker服务器 docker启动时网络情况 sy…

async与defer的区别

原文解释 async vs defer attributes - Growing with the Web

【OpenCV • c++】图像平滑处理(1) —— 线性滤波

文章目录 一、平滑处理二、图像滤波三、邻域算子与线性邻域滤波四、方框滤波代码演示 一、平滑处理 平滑处理也称为模糊处理&#xff0c;是一种简单且使用频率很高的图像处理方法&#xff0c;平滑处理的用途有很多&#xff0c;最常见的是用来减少图像上的噪点或者失真。在涉及到…