排序算法之六:快速排序(非递归)
快速排序是非常适合使用递归的,但是同时我们也要掌握非递归的算法
因为操作系统的栈空间很小,如果递归的深度太深,容易造成栈溢出
递归改非递归一般有两种改法:
- 改循环
- 借助栈(数据结构)
图示算法


不是递归,我们模拟递归的过程
代码示例
创建一个栈s,先入end,再入begin,先出左再出右
然后找这个区间的keyi,找到之后左区间就是[left,keyi-1],右区间就是[keyi+1,right]
如果区间不止一个值,那就继续入栈,单趟排序,入栈的顺序应与前面保持一致
stack
stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{int* a;int top;//标识栈顶位置int capacity;
}ST;
//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//返回栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//栈的元素个数
int STSize(ST* pst);
stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
//初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}
//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}
//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType * )realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}
//返回栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst -> a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{assert(pst);/*if (pst->top == 0){return true;}else{return false;}*/return pst->top == 0;
}
//栈的元素个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}
QuickSortNonR
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}elsebreak;}a[end + 1] = tmp;}
}
int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;if (a[begin] < a[midi]){if (a[midi] < a[end])return midi;else if (a[begin] > a[end])return begin;elsereturn end;}else{if (a[midi] > a[end])return midi;else if (a[end] > a[begin])return begin;elsereturn end;}
}
//前后指针法
int PartSort3(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int keyi = begin;int prev = begin, cur = begin + 1;while (cur <= end){//if (a[cur] < a[keyi])//{// ++prev;// Swap(&a[prev], &a[cur]);// ++cur;//}//else// ++cur;if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;return keyi;
}
void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(&s);STPush(&s, end);STPush(&s, begin);while (!STEmpty(&s)){int left = STTop(&s);STPop(&s);int right = STTop(&s);STPop(&s);int keyi = PartSort3(a, left, right);if (left < keyi - 1){STPush(&s, keyi - 1);STPush(&s, left);}if (keyi + 1 < right){STPush(&s, right);STPush(&s, keyi + 1);}}STDestroy(&s);
}
递归相当于把这些数据存到栈帧里边,而非递归是将核心区间存存到数据结构栈里面
快速排序的特性总结
- 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
- 时间复杂度:O(N*logN)
- 空间复杂度:O(logN)
- 稳定性:不稳定
相关文章:
排序算法之六:快速排序(非递归)
快速排序是非常适合使用递归的,但是同时我们也要掌握非递归的算法 因为操作系统的栈空间很小,如果递归的深度太深,容易造成栈溢出 递归改非递归一般有两种改法: 改循环借助栈(数据结构) 图示算法 不是…...
【概率方法】重要性采样
从一个极简分布出发 假设我们有一个关于随机变量 X X X 的函数 f ( X ) f(X) f(X),满足如下分布 p ( X ) p(X) p(X)0.90.1 f ( X ) f(X) f(X)0.10.9 如果我们要对 f ( X ) f(X) f(X) 的期望 E p [ f ( X ) ] \mathbb{E}_p[f(X)] Ep[f(X)] 进行估计࿰…...
MyBatis 四大核心组件之 StatementHandler 源码解析
🚀 作者主页: 有来技术 🔥 开源项目: youlai-mall 🍃 vue3-element-admin 🍃 youlai-boot 🌺 仓库主页: Gitee 💫 Github 💫 GitCode 💖 欢迎点赞…...
用Guava做本地缓存示例
缓存的作用 提升系统性能,暂时在内存中保存业务系统的数据处理结果,并且等待下次访问使用 本地缓存和分布式缓存 缓存分为本地缓存与分布式缓存。本地缓存为了保证线程安全问题,一般使用ConcurrentMap的方式保存在内存之中,而常…...
Django多对多ManyToManyField字段
Django是一个支持多对多关系的Web框架,可以在模型中定义多对多关系。多对多关系通常涉及两个实体之间的复杂交互,例如用户和组之间的关系,或者课程和学生之间的关系。在Django中,可以使用ManyToManyField字段来定义多对多关系。 …...
docker-centos中基于keepalived+niginx模拟主从热备完整过程
文章目录 一、环境准备二、主机1、环境搭建1.1 镜像拉取1.2 创建网桥1.3 启动容器1.4 配置镜像源1.5 下载工具包1.6 下载keepalived1.7 下载nginx 2、配置2.1 配置keepalived2.2 配置nginx2.2.1 查看nginx.conf2.2.2 修改index.html 3、启动3.1 启动nginx3.2 启动keepalived 4、…...
软件科技成果鉴定测试需提供哪些材料?
为了有效评估科技成果的质量,促进科技理论向实际应用转化,所以需要进行科技成果鉴定测试。申请鉴定的科技成果范围是指列入国家和省、自治区、直辖市以及国务院有关部门科技计划内的应用技术成果,以及少数科技计划外的重大应用技术成果。 …...
办公word-从不是第一页添加页码
总结 实际需要注意的是,分隔符、分节符和分页符并不是一个含义 分隔符包含其他两个;分页符:是增加一页;分节符:指将文档分为几部分。 从不是第一页插入页码1步骤 1,插入默认页码 自己可以测试时通过**…...
Android笔记(十七):PendingIntent简介
PendingIntent翻译成中文为“待定意图”,这个翻译很好地表示了它的涵义。PendingIntent描述了封装Intent意图以及该意图要执行的目标操作。PendingIntent封装Intent的目标行为的执行是必须满足一定条件,只有条件满足,才会触发意图的目标操作。…...
为 Compose MultiPlatform 添加 C/C++ 支持(2):在 jvm 平台使用 jni 实现桌面端与 C/C++ 互操作
前言 在上篇文章中我们已经介绍了实现 Compose MultiPlatform 对 C/C 互操作的基本思路。 并且先介绍了在 kotlin native 平台使用 cinterop 实现与 C/C 的互操作。 今天这篇文章将补充在 jvm 平台使用 jni。 在 Compose MultiPlatform 中,使用 jvm 平台的是 An…...
【PyTorch】卷积神经网络
文章目录 1. 理论介绍1.1. 从全连接层到卷积层1.1.1. 背景1.1.2. 从全连接层推导出卷积层 1.2. 卷积层1.2.1. 图像卷积1.2.2. 填充和步幅1.2.3. 多通道 1.3. 池化层(又称汇聚层)1.3.1. 背景1.3.2. 池化运算1.3.3. 填充和步幅1.3.4. 多通道 1.4. 卷积神经…...
qt可以详细写的项目或技术
1.QT 图形视图框架 2.QT 模型视图结构 3.QT列表显示大量信息 4.QT播放器 5.QT 编解码 6.QT opencv...
操作系统笔记——储存系统、文件系统(王道408)
文章目录 前言储存系统地址转换内存扩展覆盖交换 储存器分配——连续分配固定大小分区动态分区分配动态分区分配算法 储存器分配——非连续分配页式管理基本思想地址变换硬件快表(TLB)多级页表 段式管理段页式管理 虚拟储存器——基于交换的内存扩充技术…...
基于Html+腾讯云播SDK开发的m3u8播放器
周末业余时间在家无事,学习了一下腾讯的云播放sdk,并制作了一个小demo(m3u8播放器),该在线工具是基于腾讯的云播sdk开发的,云播sdk非常牛,可以支持多种播放格式。 预览地址 m3u8player.org 源码…...
uniapp小程序分享为灰色
引用:https://www.cnblogs.com/panwudi/p/17074172.html uniapp开发的微信小程序,没有转发,分享: 创建一个mixin:common/share.js export default {onShareAppMessage(res) { //发送给朋友return {}},onShareTimeline(res) {//…...
python:五种算法(OOA、WOA、GWO、PSO、GA)求解23个测试函数(python代码)
一、五种算法简介 1、鱼鹰优化算法OOA 2、鲸鱼优化算法WOA 3、灰狼优化算法GWO 4、粒子群优化算法PSO 5、遗传算法GA 二、5种算法求解23个函数 (1)23个函数简介 参考文献: [1] Yao X, Liu Y, Lin G M. Evolutionary programming made…...
DIP——添加运动模糊与滤波
1.运动模糊 为了模拟图像退化的过程,在这里创建了一个用于模拟运动模糊的点扩散函数,具体模糊的方向取决于输入的motion_angle。如果运动方向接近水平,则模糊效果近似水平,如果运动方向接近垂直,则模糊效果近似垂直。具…...
SQL Server查询计划(Query Plan)——SQL处理过程
6. 查询计划(Query Plan) 6.1. SQL处理过程 就SQL语句的处理过程而言,各关系库间大同小异,尤其是商业库之间实现机制和细节差别更小些,其功能及性能支持方面也更加强大和完善。SQL Server作为商业库中的后起之秀,作为SQL语句处理过程的主要支撑和保障,其优化器及相关机…...
【动手学深度学习】(十二)现代卷积神经网络
文章目录 一、深度卷积神经网络AlexNet1.理论知识 一、深度卷积神经网络AlexNet 1.理论知识 ImageNet(2010) 图片自然物体的彩色图片手写数字的黑色图片大小468 * 38728*28样本数1.2M60K类数100010 AlexNet AlexNet赢了2012ImageNet竞赛更深更大的LeNet主要改进ÿ…...
【小沐学Python】Python实现TTS文本转语音(speech、pyttsx3、百度AI)
文章目录 1、简介2、Windows语音2.1 简介2.2 安装2.3 代码 3、pyttsx33.1 简介3.2 安装3.3 代码 4、ggts4.1 简介4.2 安装4.3 代码 5、SAPI6、SpeechLib7、百度AI8、百度飞桨结语 1、简介 TTS(Text To Speech) 译为从文本到语音,TTS是人工智能AI的一个模组…...
4个维度掌控企业驱动管理:DriverStore Explorer从诊断到优化的全流程方案
4个维度掌控企业驱动管理:DriverStore Explorer从诊断到优化的全流程方案 【免费下载链接】DriverStoreExplorer Driver Store Explorer 项目地址: https://gitcode.com/gh_mirrors/dr/DriverStoreExplorer 一、问题诊断:企业环境中的驱动管理痛点…...
实测Claude 4.5 Opus重构“屎山”代码:手把手教你用AI给遗留项目做外科手术(附前后对比与单元测试生成)
实测Claude 4.5 Opus重构“屎山”代码:手把手教你用AI给遗留项目做外科手术(附前后对比与单元测试生成) 接手一个满是"祖传代码"的老旧项目,就像被丢进一座迷宫——变量命名像密码,函数逻辑像意大利面&…...
Claude Code源码阅读分享
Claude Code 源码阅读分享 链接: https://pan.baidu.com/s/1oSUWD11Yjrn5_pVVfK8Y9g?pwdv4ta Quick Start Option 1: Use with Claude Code (Recommended) # Copy agents to your Claude Code directory cp -r agency-agents/* ~/.claude/agents/# Now activate any agent in …...
丰田的“改善”到底牛在哪?-云质QMS为您解读精益生产的核心
提到丰田,大家第一反应大概率是精益生产、JIT 即时制,却很少有人深究,支撑丰田几十年持续领跑制造业的底层逻辑,其实是那个看似简单的日语词 ——改善(kaizen)。很多企业学丰田学了个皮毛,照搬流…...
C/C++ 调用约定与 Windows GDI 位图操作实用解析
stdcall调用约定 stdcall很多时候被称为pascal调用约定,因为pascal是早期很常见的一种教学用计算机程序设计语言,其语法严谨,使用的函数调用约定就是stdcall。在Microsoft C系列的C/C编译器中,常常用PASCAL宏来声明这个调用约…...
Qwen3-14B镜像部署指南:单卡RTX 4090D上快速启用中文大模型推理
Qwen3-14B镜像部署指南:单卡RTX 4090D上快速启用中文大模型推理 1. 镜像概述与核心优势 Qwen3-14B私有部署镜像是专为RTX 4090D显卡优化的中文大模型推理解决方案。这个镜像最大的特点就是"开箱即用"——所有环境依赖、模型权重、优化组件都已预装配置好…...
Kimi-VL-A3B-Thinking开源大模型部署教程:MoonViT视觉编码器实测解析
Kimi-VL-A3B-Thinking开源大模型部署教程:MoonViT视觉编码器实测解析 1. 模型简介与核心能力 Kimi-VL-A3B-Thinking是一款创新的开源混合专家(MoE)视觉语言模型(VLM),在多模态推理领域展现出卓越性能。这…...
别再只建网站了!宝塔面板的‘Node项目’功能,让你的Express/Koa后端服务上线更简单
解锁宝塔面板的隐藏技能:Node.js后端服务一键部署实战指南 你是否还在为Node.js项目的繁琐部署流程而头疼?手动配置PM2、Nginx反向代理、环境变量设置...这些操作不仅耗时耗力,还容易出错。其实,你每天都在使用的宝塔面板早已内置…...
如何突破Office功能限制?本地化激活方案全解析
如何突破Office功能限制?本地化激活方案全解析 【免费下载链接】ohook An universal Office "activation" hook with main focus of enabling full functionality of subscription editions 项目地址: https://gitcode.com/gh_mirrors/oh/ohook 当…...
ai辅助开发,让快马平台智能优化你的openclaw脚本安全性与性能
今天想和大家分享一个实用技巧:如何用AI辅助开发,在InsCode(快马)平台上优化openclaw脚本的安全性与性能。最近我需要一个能智能清理下载文件夹的脚本,但又要避免误删重要文件,这个需求让我深刻体会到AI辅助开发的便利性。 需求分…...
