排序算法6---快速排序(非递归)(C)
回顾递归的快速排序,都是先找到key中间值,然后递归左区间,右区间。
那么是否可以实现非递归的快排呢?答案是对的,这里需要借助数据结构的栈。将右区间左区间压栈(后进先出),然后取出左区间,再将左区间的子右区间和子左区间压栈,再取出左区间的子左区间......,当栈为空时,即全部取出,此时已经有序。
和递归一样,首先用三数取中来优化:
//三数取中
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);
}
相关文章:
排序算法6---快速排序(非递归)(C)
回顾递归的快速排序,都是先找到key中间值,然后递归左区间,右区间。 那么是否可以实现非递归的快排呢?答案是对的,这里需要借助数据结构的栈。将右区间左区间压栈(后进先出),然后取出…...
【Verilog】期末复习——设计带异步清零且高电平有效的4位循环移位寄存器
系列文章 数值(整数,实数,字符串)与数据类型(wire、reg、mem、parameter) 运算符 数据流建模 行为级建模 结构化建模 组合电路的设计和时序电路的设计 有限状态机的定义和分类 期末复习——数字逻辑电路分…...
银行网络安全实战对抗体系建设实践
文章目录 前言一、传统攻防演练面临的瓶颈与挑战(一)银行成熟的网络安全防护体系1、缺少金融特色的演练场景设计2、资产测绘手段与防护体系不适配3、效果评价体系缺少演练过程维度相关指标 二、实战对抗体系建设的创新实践(一)建立…...
SwiftUI之深入解析Alignment Guides的超实用实战教程
一、Alignment Guide 简介 Alignment guides 是一个强大的布局工具,但通常未被充分利用。在很多情况下,它们可以帮助我们避免更复杂的选项,比如锚点偏好。如下所示,对对齐的更改也可以自动(并且容易地)动画…...
java获取视频文件的编解码器
java获取视频文件的编解码器 引入jar包: <dependency><groupId>org.bytedeco</groupId><artifactId>javacv-platform</artifactId><version>1.5.9</version></dependency>测试类 package com.jd.brand.approve.…...
动态规划Day06(完全背包)
完全背包 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同…...
selenium之框架之窗口
...
华为OD机试 - 最小矩阵宽度(Java JS Python C)
题目描述 给定一个矩阵,包含 N * M 个整数,和一个包含 K 个整数的数组。 现在要求在这个矩阵中找一个宽度最小的子矩阵,要求子矩阵包含数组中所有的整数。 输入描述 第一行输入两个正整数 N,M,表示矩阵大小。 接下来 N 行 M 列表示矩阵内容。 下一行包含一个正整数 K…...
嵌入式linux_C应用学习之API函数
1.文件IO 1.1 open打开文件 #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> int open(const char *pathname, int flags); int open(const char *pathname, int flags, mode_t mode);pathname:字符串类型,用于标…...
【ubuntu】docker中如何ping其他ip或外网
docker中如何ping其他ip或外网 示例图: 运行下面命令: docker run -it --namehei busybox看情况需要加权限 sudo,即: sudo docker run -it --namehei busyboxping 外网 ping -c 4 www.baidu.comping 内网 ping -c 4 192.168.…...
【Vue3+Ts项目】硅谷甄选 — 品牌管理+平台属性管理+SPU管理+SKU管理
一、品牌管理模块 1.1 静态模块搭建 使用到element-plus的card、button、table、pagination等组件:src/views/product/trademark/index.vue <template><el-card><!-- 卡片顶部添加品牌按钮 --><el-button type"primary" size&quo…...
计算机图形学流体模拟 blender 渲染脚本
做流体模拟的时候,想要复现别人的成果,但是别人的代码都是每帧输出 ply 格式的文件,渲染部分需要自己完成 看了一下,似乎用 blender 是最简单的,于是记录一下过程中用到的代码 Blender 版本 4.0 批量导入 ply 假设…...
二分图带权最大匹配-KM算法详解
文章目录 零、前言一、红娘再牵线二、二分图带权最大完备匹配2.1二分图带权最大匹配2.2概念2.3KM算法2.3.1交错树2.3.2顶标2.3.3相等子图2.3.4算法原理2.3.5算法实现 三、OJ练习3.1奔小康赚大钱3.2Ants 零、前言 关于二分图:二分图及染色法判定-CSDN博客 关于二分…...
Redis命令 - Sets命令组常用命令
Set集合,无序,一堆不重复值的组合。利用redis提供的set数据结构,可以存储一些集合性的数据。 使用场景:例如,实现如共同关注、共同喜好、二度好友等 1、SADD key member [member …] 向集合中添加一个或者多个成员 …...
DA14531-外设驱动篇-I2C通信应用
文章目录 1.I2C通信应用相关文件2.宏定义列表3.主要函数接口4.应用代码实例1.I2C通信应用相关文件 1)i2c.c和i2c.h(SDK文件) 2)app_I2cProtocol.c和app_I2cProtocol.h(用户应用文件) 2.宏定义列表 宏定义注解I2C_ADDRESSING_7B7-bit 地址I2C_ADDRESSING_10B10-bit 地址…...
Git仓库管理笔记
问题: hint: the same ref. If you want to integrate the remote changes, use Done 解决: 解决方法: 1、先使用pull命令: git pull --rebase origin master 2、再使用push命令: git push -u origin master...
[嵌入式软件][入门篇] 搭建在线仿真平台(STM32)
文章目录 一、注册平台二、创建首个项目三、硬件介绍 一、注册平台 进入官方,进行注册: 在线仿真地址 二、创建首个项目 ① 新建项目 ② 搭建一个电路 ③ 用STM32F103搭建一个简单电路 ④ 进入编码界面 三、硬件介绍 红框是必看文档ÿ…...
设置5台SSH互免的虚拟机服务器配置
搭建一套集群虚拟机,往往都需要互免设置,过程很简单,避免以后再搭建还得网上搜索,我直接将这一个步骤写成笔记,记录下来,方便后续查阅。 步骤如下—— 1、准备五台机器 服务器名字服务器IPhadoop1192.16…...
深信服技术认证“SCCA-C”划重点:交付和运维体系
为帮助大家更加系统化地学习云计算知识,高效通过云计算工程师认证,深信服特推出“SCCA-C认证备考秘笈”,共十期内容。“考试重点”内容框架,帮助大家快速get重点知识。 划重点来啦 *点击图片放大展示 深信服云计算认证ÿ…...
xlua源码分析(五) struct类型优化
xlua源码分析(五) struct类型优化 上一节我们分析了xlua是如何实现lua层访问C#值类型的,其中我们重点提到了xlua默认实现方式下,struct访问的效率问题。实际上,xlua还提供了两种优化的方式,可以大大提高str…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
