排序算法6---快速排序(非递归)(C)

        回顾递归的快速排序,都是先找到key中间值,然后递归左区间,右区间。

        那么是否可以实现非递归的快排呢?答案是对的,这里需要借助数据结构的。将右区间左区间压栈(后进先出),然后取出左区间,再将左区间的子右区间和子左区间压栈,再取出左区间的子左区间......,当栈为空时,即全部取出,此时已经有序。f2411c060f1945129eabf66cf4da911c.png

5b3c8442dda544c1a16c2f3b9d702693.png 

 

        和递归一样,首先用三数取中来优化:

//三数取中
int GetMidi(int* arr, int begin, int end)
{int midi = (begin + end) / 2;if ((arr[begin] > arr[midi] && arr[begin] < arr[end])|| (arr[begin]) > arr[end] && arr[begin] < arr[midi])midi = begin;if ((arr[end] > arr[midi] && arr[end] < arr[begin])|| (arr[end]) > arr[begin] && arr[end] < arr[midi])midi = end;return midi;
}

        接着借用递归快排的指针法,来进行单趟排序,得到中间基准值,并划分做右区间(不记得指针法的回看博客)

int QuickSort_pointer_incline(int* arr, int begin, int end)
{int midi = GetMidi(arr, begin, end);Swap(&arr[begin], &arr[midi]);int keyi = begin;int prev = begin, cur = prev + 1;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur)Swap(&arr[prev], &arr[cur]);++cur;}Swap(&arr[prev], &arr[keyi]);keyi = prev;return keyi;
}

        最后使用栈来压栈出栈

void QuickSort_NonR_incline(int* arr, int begin, int end)
{ST s;STInit(&s);//放入端点//因为后进先出,所以先入右,后入左,区间[左,右]STPush(&s, end);STPush(&s, begin);while (!STEmpyty(&s)){//出栈int left = STTop(&s);STPop(&s);int right = STTop(&s);STPop(&s);//指针单趟排序int keyi = QuickSort_pointer_incline(arr, left, right);//[left,keyi-1],keyi,[keyi+1,right]//入右区间,同样先入右区间的右端点,再左端点if (keyi + 1 < right){STPush(&s, right);STPush(&s, keyi + 1);}//入左区间,同样先入左区间的右端点,再左端点if (left < keyi - 1){STPush(&s, keyi - 1);STPush(&s, left);}//循环回去,又取出区间,再次单趟排序后,又入子右区间,子左区间}STDestroy(&s);
}

 

 

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

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

相关文章

详细讲解Python连接Mysql的基本操作

目录 前言1. mysql.connector2. pymysql 前言 连接Mysql一般有几种方法&#xff0c;主要讲解mysql.connector以及pymysql的连接 后续如果用到其他库还会持续总结&#xff01; 对于数据库中的表格,本人设计如下:(为了配合下面的操作) 1. mysql.connector mysql.connector 是一…

C#,入门教程(19)——循环语句(for,while,foreach)的基础知识

上一篇&#xff1a; C#&#xff0c;入门教程(18)——分支语句&#xff08;switch-case&#xff09;的基础知识https://blog.csdn.net/beijinghorn/article/details/124039953 一、for循环 当老师进入教室&#xff0c;从门口开始分别按行、列点名&#xff0c;看看哪位翘课&…

Xcode15 升级问题记录

这里写自定义目录标题 新版本Xcode15升级问题1&#xff1a;rsync error: some files could not be transferred (code 23) at ...参考 新版本Xcode15升级 下载地址&#xff1a;https://developer.apple.com/download/all/ 我目前使用的版本是Xcode15.2 我新创建了一个项目&…

transfomer中Decoder和Encoder的base_layer的源码实现

简介 Encoder和Decoder共同组成transfomer,分别对应图中左右浅绿色框内的部分. Encoder&#xff1a; 目的&#xff1a;将输入的特征图转换为一系列自注意力的输出。 工作原理&#xff1a;首先&#xff0c;通过卷积神经网络&#xff08;CNN&#xff09;提取输入图像的特征。然…

开发需求总结9-el-tree获取选中节点,节点全选时返回被全选子级的父节点,未全选则返回被选中的节点

目录 需求描述 代码实现&#xff1a; 需求描述 需要获取树组件选中的节点&#xff0c;假如父节点被选中&#xff08;该节点全选&#xff09;&#xff0c;即只返回父节点的数据&#xff0c;如父节点未被全选&#xff0c;则正常返回被选中节点的数据。 示例一&#xff1a; 如上图…

Python展示 RGB立方体的二维切面视图

代码实现 import numpy as np import matplotlib.pyplot as plt# 生成 24-bit 全彩 RGB 立方体 def generate_rgb_cube():# 初始化一个 256x256x256 的三维数组rgb_cube np.zeros((256, 256, 256, 3), dtypenp.uint8)# 填充立方体for r in range(256):for g in range(256):fo…

编曲混音FL Studio21.2对电脑有什么配置要求

FL Studio 21是一款非常流行的音乐制作软件&#xff0c;它可以帮助音乐人和制作人创作出高质量的音乐作品。然而&#xff0c;为了保证软件的稳定性和流畅性&#xff0c;用户需要知道FL Studio 21对电脑的配置要求。本文将介绍FL Studio 21的配置要求&#xff0c;以帮助用户选择…

32 二叉树的定义

之前的通用树结构 采用双亲孩子表示法模型 孩子兄弟表示法模型 引出二叉树 二叉树的定义&#xff1a; 满二叉树和完全二叉树 对此图要有印象 满二叉树一定是完全二叉树&#xff0c;但是完全二叉树不一定是满二叉树 小结

RabbitMQ交换机(2)-Direct

1.Direct 直连(路由)交换机,生产者将消息发送到交换机&#xff0c;并指定消息的Routing Key&#xff08;路由键&#xff09;。交换机会将Routing Key与队列绑定进行匹配&#xff0c;如果匹配成功&#xff0c;则将该消息路由到对应的队列中。如果没有匹配成功&#xff0c;该消息…

小程序中使用微信同声传译插件实现语音识别、语音合成、文本翻译功能----语音识别(一)

官方文档链接&#xff1a;https://mp.weixin.qq.com/wxopen/plugindevdoc?appidwx069ba97219f66d99&token370941954&langzh_CN#- 要使用插件需要先在小程序管理后台的设置->第三方设置->插件管理中添加插件&#xff0c;目前该插件仅认证后的小程序。 语音识别…

JS | JS调用EXE

JS | JS调用EXE 网上洋洋洒洒一大堆文章提供,然我还是没找打合适的方案: 注册表方案做了如下测试(可行但是不推荐?): 先,键入文件名为 myprotocal.reg 的注册表,并键入一下信息: Windows Registry Editor Version 5.00[HKEY_CLASSES_ROOT\openExe] //协议名…

Redis相关命令详解及其原理

Redis概念 Redis&#xff0c;英文全称是remote dictionary service&#xff0c;也就是远程字典服务。这是kv存储数据库。Redis&#xff0c;包括所有的数据库&#xff0c;都是请求-回应模式&#xff0c;通俗来说就是数据库不会主动地要给前台推送数据&#xff0c;只有前台发送了…

MySQL/Oracle 的 字符串拼接

目录 MySQL、Oracle 的 字符串拼接1、MySQL 的字符串拼接1.1 CONCAT(str1,str2,...) : 可以拼接多个字符串1.2 CONCAT_WS(separator,str1,str2,...) : 指定分隔符拼接多个字符串1.3 GROUP_CONCAT(expr) : 聚合函数&#xff0c;用于将多行的值连接成一个字符串。 2、Oracle 的字…

广州市生物医药及高端医疗器械产业链大会暨联盟会员大会召开,天空卫士数据安全备受关注

12月20日&#xff0c;广州市生物医药及高端医疗器械产业链大会暨联盟会员大会在广州举办。在本次会议上&#xff0c;作为大会唯一受邀参加主题分享的技术供应商&#xff0c;天空卫士南区技术总监黄军发表《生物制药企业如何保护数据安全》的主题演讲。 做好承上启下“连心桥”…

C++设计模式-- 2.代理模式 和 外观模式

文章目录 代理模式外观模式角色和职责代码演示一&#xff1a;代码演示二&#xff1a;外观模式适用场景 代理模式 代理模式的定义&#xff1a;为其他对象提供一种代理以控制对这个对象的访问。在某些情况下&#xff0c;一个对象不适合 或不能直接引用另一个对象&#xff0c;而代…

【实战记录】 vagrant+virtualbox+docker 轻松用虚拟机集成组件

用途 最近要学一大堆组件&#xff0c;不想直接安装本机上&#xff0c;然后gpt说&#xff1a;你可以用vagrant起个虚拟机&#xff08;然后docker拉取各种组件的镜像&#xff09;&#xff1b;或者k8s 实战的整体思路 首先安装virtualbox和vagrant。然后cmd依次键入三条命令 安…

无需编程,简单易上手的家具小程序搭建方法分享

想要开设一家家具店的小程序吗&#xff1f;现在&#xff0c;我将为大家介绍如何使用乔拓云平台搭建一个家具小程序&#xff0c;帮助您方便快捷地开展线上家具销售业务。 第一步&#xff0c;登录乔拓云平台进入商城后台管理页面。 第二步&#xff0c;在乔拓云平台的后台管理页面…

云畅科技技术中心被认定为湖南省省级企业技术中心

近日&#xff0c;湖南省工业和信息化厅公布《2023年第二批湖南省省级企业技术中心(第29批)》&#xff0c;云畅科技技术中心作为研发设计型代表入选。 省级企业技术中心是强化企业技术创新主体地位&#xff0c;增强企业自主创新能力&#xff0c;推动工业企业高质量发展的一个重要…

深圳三维扫描分析/偏差检测模具型腔三维尺寸及形位偏差测量公司

CASAIM中科广电三维扫描模具型腔深圳案例&#xff1a; 模具型腔的三维扫描分析/偏差检测是一项重要的质量控制过程&#xff0c;旨在确保模具制造过程中的精确度和一致性。 CASAIM中科广电通过使用高精度的三维扫描设备&#xff0c;可以获取模具型腔的实际形状和尺寸数据&…

使用vue快速开发一个带弹窗的Chrome插件

vue-chrome-extension-quickstart 说在前面 &#x1f388;平时我们使用Chrome插件通常都只是用来编写简单的js注入脚本&#xff0c;大家有没有遇到过需要插件在页面上注入一个弹窗呢&#xff1f;比如我们希望可以通过快捷键快速唤起ChatGPT面板或者快速唤起一个翻译面板&#x…