手把手教你快速排序(非递归)

2023-10-29

目录

一.实现原理

 二.代码实现(c语言)


今天小编带大家学习快速排序的非递归方法,当然这篇博客是基于大家已经掌握了快排的递归方法的,如果还有不会的童鞋,可以看看下面这篇博客呦~: 手把手教你快速排序(递归)

一.实现原理

首先我们需要一个栈。

我们知道,快速排序就是一个递归加分治的思想,在递归方法里,我们是把数列分成两部分,每个部分又分成两部分,直到不能再分为止。

所以我们可以用一个栈来存放数列两部分的头尾,排一次就让头尾出来,再把分好的两部分的头尾分别再入栈,再排再出,再入,直到不能再分成两部分为止。

原理图:

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCx6KaBIOWuheWcqOWutg==,size_20,color_FFFFFF,t_70,g_se,x_16

 二.代码实现(c语言)

int _quickSortNonr(int* a, int left, int right)//栈实现快排子函数
{
	int pivot = left;
	int begin = left, end = right, key = a[left];
	while (begin < end)
	{
		while (begin < end && a[end] >= key) end--;
		a[pivot] = a[end];
		pivot = end;
		while (begin < end && a[begin] <= key) begin++;
		a[pivot] = a[begin];
		pivot = begin;
	}
	a[pivot] = key;
	return pivot;
}
void quickSortNonr(int* a, int left, int right)//栈实现快排,非递归
{
	stack<int> st;//C++ STL->#include<stack>
	st.push(right);
	st.push(left);
	while (!st.empty())
	{
		int _left = st.top();
		st.pop();
		int _right = st.top();
		st.pop();
		int mid = _quickSortNonr(a, _left, _right);
		if (mid + 1 < _right)
		{
			st.push(_right);
			st.push(mid + 1);
		}
		if (_left < mid - 1)
		{
			st.push(mid - 1);
			st.push(_left);
		}
	}
}


如有错误,敬请斧正,恳请点赞支持

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

手把手教你快速排序(非递归) 的相关文章

  • 蒙牛×每日互动合作获评中国信通院2023“数据+”行业应用优秀案例

    当前在数字营销领域 品牌广告主越来越追求品效协同 针对品牌主更注重营销转化的切实需求 数据智能上市企业每日互动 股票代码 300766 发挥自身数据和技术能力优势 为垂直行业的品牌客户提供专业的数字化营销解决方案 颇受行业认可 就在不久前举
  • Freertos低功耗管理

    空闲任务中的低功耗Tickless处理 在整个系统运行得过程中 其中大部分时间都是在执行空闲任务的 空闲任务之所以执行 因为在系统中的其他任务处于阻塞或者被挂起时才会执行 因此可以将空闲任务的执行时间转换成低功耗模式 在其他任务解除阻塞而准
  • /lib64/libstdc++.so.6库缺失

    问题 lib64 libstdc so 6 version CXXABI 1 3 8 not found lib64 libstdc so 6 version CXXABI 1 3 9 not found lib64 libstdc so
  • 华为OD机试真题-计算三叉搜索树的高度-2023年OD统一考试(C卷)

    题目描述 定义构造三叉搜索树规则如下 每个节点都存有一个数 当插入一个新的数时 从根节点向下寻找 直到找到一个合适的空节点插入 查找的规则是 1 如果数小于节点的数减去500 则将数插入节点的左子树 2 如果数大于节点的数加上500 则将数
  • 【质量-弹簧-阻尼系统】基于脉冲响应约束的子空间辨识研究(Matlab代码实现)

    欢迎来到本博客 博主优势 博客内容尽量做到思维缜密 逻辑清晰 为了方便读者 座右铭 行百里者 半于九十 本文目录如下 目录 1 概述 2 运行结果 3 参考文献 4 Matlab代码 数据 文章
  • 牛客字符串

    提示 文章写完后 目录可以自动生成 如何生成可参考右边的帮助文档 文章目录 前言 一 pandas是什么 二 使用步骤 1 引入库 2 读入数据 总结 前言 提示 这里可以添加本文要记录的大概内容 例如 随着人工智能的不断发展 机器学习这门
  • 【C++入门】C++ STL中string常用函数用法总结

    目录 前言 1 string使用 2 string的常见构造 3 string类对象的访问及遍历 迭代器遍历 访问 4 string类对象的容量操作 4 1 size和length 4 2 clear empty和capacity 4 3
  • 排序:计数排序

    一 概念 计数排序是非比较排序 是对哈希直接定址法的变形应用 二 思想 利用数组统计相同数据出现的次数 例如整型数据m出现n次 就在数组m位置记录数据为n 最后从头遍历数组打印数据即可 通俗来讲就是 数组下标即为数据 下标所指位置的值即为数
  • 华为OD机试2024年最新题库(C++)

    我是一名软件开发培训机构老师 我的学生已经有上百人通过了华为OD机试 学生们每次考完试 会把题目拿出来一起交流分享 重要 2024年1月 5月 考的都是OD统一考试 C卷 题库已经整理好了 命中率95 以上 这个专栏使用 C 解法 问1 考
  • 华为OD机试真题-API集群负载统计-Java-OD统一考试(C卷)

    题目描述 某个产品的RESTful API集合部署在服务器集群的多个节点上 近期对客户端访问日志进行了采集 需要统计各个API的访问频次 根据热点信息在服务器节点之间做负载均衡 现在需要实现热点信息统计查询功能 RESTful API的由多
  • 华为OD机试2024年最新题库(Python)

    我是一名软件开发培训机构老师 我的学生已经有上百人通过了华为OD机试 学生们每次考完试 会把题目拿出来一起交流分享 重要 2024年1月 5月 考的都是OD统一考试 C卷 题库已经整理好了 命中率95 以上 这个专栏使用 Python解法
  • 矩阵基本操作

    问题描述 已知一个n n的矩阵 方阵n lt 100 把矩阵主副对角线上的元素值加上x 然后输出这个新矩阵 输入格式 一行两个变量 用空格隔开 代表n和x 接下来的n行每行n列 表示矩阵的数值 用空格隔开 输出格式 输出新矩阵 每个数字5个
  • 矩阵基本操作2

    题目描述 问题描述 将方阵 n 行n列 n lt 100 置成下三角矩阵 主对角线右上角数字全部清零 输入格式 第一行输入n 接下来的n行每行n列 表示矩阵的数值 用空格隔开 输出格式 n行n列下三角矩阵 每个数字3个占位符 左对齐 输入样
  • ​LeetCode解法汇总82. 删除排序链表中的重复元素 II

    目录链接 力扣编程题 解法汇总 分享 记录 CSDN博客 GitHub同步刷题项目 https github com September26 java algorithms 原题链接 力扣 LeetCode 描述 给定一个已排序的链表的头
  • 做大模型也有1年多了,聊聊这段时间的感悟!

    自ChatGPT问世以来 做大模型也有1年多了 今天给大家分享这一年后的感悟 过去一年应该是AI圈最万千瞩目的一年了 大家对大模型 OpenAI ChatGPT AI Native Agent这些词投入了太多的关注 以至于有一年的时间好像经
  • 机器学习算法实战案例:时间序列数据最全的预处理方法总结

    文章目录 1 缺失值处理 1 1 统计缺失值 1 2 删除缺失值 1 3 指定值填充 1 4 均值 中位数 众数填充
  • 「优选算法刷题」:快乐数

    一 题目 编写一个算法来判断一个数 n 是不是快乐数 快乐数 定义为 对于一个正整数 每一次将该数替换为它每个位置上的数字的平方和 然后重复这个过程直到这个数变为 1 也可能是 无限循环 但始终变不到 1 如果这个过程 结果为 1 那么这个
  • 【固定翼飞机】基于最优控制的固定翼飞机着陆控制器设计研究(Matlab代码实现)

    欢迎来到本博客 博主优势 博客内容尽量做到思维缜密 逻辑清晰 为了方便读者 座右铭 行百里者 半于九十 本文目录如下 目录 1 概述 2 运行结果 3 参考文献 4 Matlab代码及文章
  • 2024年华为OD机试真题-虚拟游戏理财-Python-OD统一考试(C卷)

    题目描述 在一款虚拟游戏中生活 你必须进行投资以增强在虚拟游戏中的资产以免被淘汰出局 现有一家Bank 它提供有若干理财产品m 风险及投资回报不同 你有N 元 进行投资 能接受的总风险值为X 你要在可接受范围内选择最优的投资方式获得最大回报
  • 【一种新的Burton-Miller型奇异边界方法(BM-SBM)】用于声学设计灵敏度分析,2D和3D声学设计灵敏度分析的奇异边界方法研究(Matlab代码实现)

    欢迎来到本博客 博主优势 博客内容尽量做到思维缜密 逻辑清晰 为了方便读者 座右铭 行百里者 半于九十 本文目录如下 目录 1 概述 2 运行结果 2 1 2D 2 2 3D

随机推荐

  • 前端ps切图,图文教程,详细。

    写在前面 本文主要内容是目前我所知道的切图技巧结合网上的资料 写出来分享一波 图文教程 多图 BB 很多人都会说 切图这个活倒底分给UI还是分给前端 虽然好的UI会给我们把图切好 但是他们切的图不一定百分之百符合我们的需求 所以我一直都觉得
  • Thinkpad win11截图快捷键win + sihft +s无反应

    参考 l联想知识库 Win11截图快捷键win shift s按了没反应 省流 关闭自动设置时间 在手动设置日期和时间改为2021年10月30日 再按Shift Ctrl S 此时可以截图成功 然后再开启自动设置时间 再按Shift Ctr
  • 深度学习(一)——MP神经元模型, BP算法, 神经元激活函数, Dropout

    https antkillerfarm github io 前言 神经网络本质上不是什么新东西 十年前 我还在上学的时候 就接触过皮毛 然而那时这玩意更多的还是学术界的屠龙之术 工业界几乎没有涉及 及至近日重新拾起 方才发现 这十年正是神经
  • 【Linux】ubuntu安装samba服务器

    Linux安装samba服务器 前言 正文 前言 在VMware虚拟机中安装samba服务器 可以用于windows与虚拟机文件夹共享 虽然VMware自带文件传输的工具 但是如果换一个环境换一个虚拟机工具就不一定具备该功能 所以samba
  • 常见的并发问题有哪些都不知道,还怎么说自己是大佬!!

    常见的并发问题有哪些 1 并发测试 1 1并发测试的定义 1 2并发测试的分类 2 常见并发问题 2 1事务并发的问题 2 2极限值并发的问题 2 3压力并发的问题 2 4异常数据干扰并发的问题 1 并发测试 最近小屌丝一直在埋头苦练性能的
  • 【云原生 · k8s】k8s-master初始化过程讲解

    文章目录 1 k8s master初始化过程讲解 2 k8s master运行的组件查看 控制平面 官网说法 查看 3 此时主节点就可以用 4 加入k8s node到集群中 5 k8s master主节点 查看所有工作节点的信息 6 如何让
  • Python爬虫抓取岗位信息~~叮~~毕业生看过来

    众所周知爬虫是用python编程语言实现的 主要用于网络数据的抓取和处理 例如爬取豆瓣电影TOP250 爬取小说等等 而爬取岗位对于刚毕业的大学生也是非常有必要的 下面我们来看看如何实现吧 用到的编程工具是python3 7 目录 一 抓取
  • Cocos2d-x2.0 进度动画 深入分析http://www.oschina.net/question/565065_101742

    Cocos2d x2 0 进度动画 深入分析 长平狐 发表于 2013 3 19 18 39 8个月前 0回 181阅 开源中国诚邀您参加 Cloud Foundry 中国群英会 北京 上海 杭州 成都 深圳 Cocos2d x相关教程来源
  • Apache下的ArrayUtils工具类总结(操作数组)

    ArrayUtils中的方法 1 add 将给定的数据添加到指定的数组中 返回一个新的数组 2 addAll 合并两个数组 3 contains 检查该数据在该数组中是否存在 返回一个boolean值 4 getLength 返回该数组长度
  • 手把手教你快速排序(非递归)

    目录 一 实现原理 二 代码实现 c语言 今天小编带大家学习快速排序的非递归方法 当然这篇博客是基于大家已经掌握了快排的递归方法的 如果还有不会的童鞋 可以看看下面这篇博客呦 手把手教你快速排序 递归 一 实现原理 首先我们需要一个栈 我们
  • Python:数组添加数据和删除数据

    行添加 删除数据 valid tmp np append valid tmp train tmp idx axis 0 train tmp idx 和valid tmp维数相同 train tmp np delete train tmp i
  • 计算机页码格式罗马数字,word 页码 罗马数字怎么从1开始

    word 页码 罗马数字怎么从1开始以下文字资料是由 历史新知网www lishixinzhi com 小编为大家搜集整理后发布的内容 让我们赶快一起来看一下吧 word 页码 罗马数字怎么从1开始 第一步 在前几页结束的地方点 插入 gt
  • 华为OD机试真题-区块链转储系统【2023Q1】

    题目描述 区块链底层存储是一个链式文件系统 由顺序的N个文件组成 每个文件的大小不一 依次为F1 F2 Fn 随着时间的推移 所占存储会越来越大 云平台考虑将区块链按文件转储到廉价的SATA盘 只有连续的区块链文件才能转储到SATA盘上 且
  • 将安全信息应用到以下对象时发生错误:C:\Users\lenovo\Application Data无法枚举容器中的对象。访问被拒绝。

    如果找不到Application Data 打开访问权限 右键属性 gt gt 安全 gt gt 高级 更改 高级 然后 确定 gt gt 确定 gt gt 应用 然后回到 应用 这样就能进入Application Data文件夹了
  • 等待和通知机制(wait和notify)

    1 等待和通知机制的实现 wait 方法 wait 是 Object 类的方法 它的作用是使当前执行wait方法的线程进行等待 该方法将当前线程置入 预执行队列 中 并在 wait 所在的代码行处停止执行 直到接到通知或者被中断才能继续执行
  • 代表什么_鸽子飞到家里代表什么

    阅读本文前 请您先点击上面的蓝色字体 教你风水旺财运 再点击 关注 这样您就可以继续免费收到最新资讯了 每天都有分享 完全是免费订阅 请放心关注 现在可能没那么常见 但是在农村家里出现一些外来的生物还是很正常的 对我们也存在影响 对我们来说
  • 【干货】MySQL底层架构设计,你了解多少?

    很多开发同学对SQL优化如数家珍 却对MySQL架构一知半解 岂不是只见树叶 不见森林 终将陷入细节中不能自拔 今天就一块学习MySQL分层架构 深入了解MySQL底层实现原理 以及每层的作用 我们常见的SQL优化到底在哪一层做了优化 小伙
  • vs code使用power mode设置鼠标光标动效

    记录一个开发的题外话 vs code编辑器使用插件 power mode来设置鼠标光标动效 如下 1 vscode 安装 power mode插件 2 打开vscode编辑器 文件 首选项 设置 设置界面 开启power mode插件 设置
  • [Pyhon疫情大数据分析] 三.新闻信息抓取及词云可视化、文本聚类和LDA主题模型文本挖掘

    思来想去 虽然很忙 但还是挤时间针对这次肺炎疫情写个Python大数据分析系列博客 包括网络爬虫 可视化分析 GIS地图显示 情感分析 舆情分析 主题挖掘 威胁情报溯源 知识图谱 预测预警及AI和NLP应用等 希望该系列线上远程教学对您有所
  • 数据结构 算法大全 基础篇

    数据结构和算法是计算机科学中的两个重要部分 它们对于编写高效 可扩展性强的程序非常重要 数据结构是一种组织和存储数据的方式 它包括一些基本的数据结构 例如数组 链表 栈 队列 树 图等等 数据结构的选择取决于所要解决的问题和使用场景 因此需