当前位置: 首页 > news >正文

每日回顾:简单用C写 冒泡排序、快速排序

冒泡排序

冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

//冒泡排序
void BubbleSort(int* a, int n) {for (int i = 0; i < n - 1; i++) {	//冒泡 n-1 次bool flag = false;for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {Swap(&a[j], &a[j + 1]);}flag = true;}if (!flag) {break;}}
}

时间复杂度

O(n^2)

空间复杂度

原地修改,O(1)

快速排序

快速排序(Quick Sort)是一种高效的排序算法,由C. A. R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer):通过一个划分操作将数据分为独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再递归地对这两部分数据分别进行排序操作。

递归版本

递归版本一:hoare

大致思想:通过左右下标指针不断的寻找交换,每趟分割可以将 1 个 a[keyi] 归位;递归地分割、归位子序列即可

右下标指针 right 从右开始寻找小于 a[keyi] 的值,左下标指针 left 从左开始寻找大于 a[keyi] 的值;然后交换 a[left] 和 a[right],继续寻找直到 left 和 right 相遇,将 a[keyi] 归位

//单趟分割区间
int PartSort_1(int* a, int left, int right) {int keyi = 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 QuickSort(int* a, int begin, int end) {//只有一个元素,或区间不存在if (begin >= end) {return;}//分割区间int midi = PartSort_1(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi+1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi + 1, end);}

递归版本二:挖坑法

大致思想:hoare法是大小交换,而挖坑法是找到小了立即交换到左边,找到大了立即交换到右边,hole(坑)的值由 key 保存,坑的位置随着值的交换而变化

//单趟分割区间
//挖坑法
int PartSort_2(int* a, int left, int right) {int key = a[left];	//保存被挖坑的值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 hole;
}//快速排序
void QuickSort(int* a, int begin, int end) {//只有一个元素,或区间不存在if (begin >= end) {return;}//分割区间//int midi = PartSort_1(a, begin, end);int midi = PartSort_2(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi+1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi + 1, end);
}

递归版本三:前后指针法

大致思想:通过 prev 和 cur 下标指针,将每趟大于等于 a[keyi] 的值往后推,最后将基准值 a[keyi] 与 a[prev] 交换归位

//单趟分割区间
//前后指针法
int PartSort_3(int* a, int left, int right) {int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right) {cur 找小//while (cur < right && a[cur] >= a[keyi]) {//	cur++;//}//if (cur < right) {	//避免所有元素都大于 keyi//	prev++;//	Swap(&a[cur], &a[prev]);//}if (a[cur] < a[keyi]) {prev++;Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[keyi], &a[prev]);return prev;
}//快速排序
void QuickSort(int* a, int begin, int end) {//只有一个元素,或区间不存在if (begin >= end) {return;}//分割区间//int midi = PartSort_1(a, begin, end);//int midi = PartSort_2(a, begin, end);int midi = PartSort_3(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi+1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi + 1, end);
}

时间复杂度(三个版本效率相同)

每趟区间分割创建函数栈帧的复杂度为二叉结构的高度 O(logn),每趟区间分割确定一个数的位置 O(n),所以是 O(n*logn)

但是如果数组有大量重复元素时,每次选择的 keyi 基准值都是同一个数;或者每次选择的 keyi 都是数组中最大或最小的元素,那么递归深度就会大大增加,时间复杂度变成 O(n^2),比如下面的示意图

空间复杂度(三个版本效率相同)

取决于递归深度,即二叉结构高度 O(logn)

稳定性

涉及到元素之间的交换,不稳定

递归版本的优化

为了避免取基准值 keyi 时,出现取到最小或最大的情况,我们使用三数取中的方法

//三数取中
int GetMidIndex(int* a, int left, int right) {int midi = (left + right) / 2;if (a[left] > a[midi]) {Swap(&a[left], &a[midi]);	//此时 a[left] <= a[midi]}if (a[left] > a[right]) {Swap(&a[left], &a[right]);	//此时 a[left] <= a[right]}if (a[midi] > a[right]) {Swap(&a[right], &a[midi]);	//此时 a[midi] <= a[right]}return midi;
}

以版本三为例,应用

//单趟分割区间
//前后指针法
int PartSort_3(int* a, int left, int right) {int keyi = GetMidIndex(a, left, right);Swap(&a[keyi], &a[left]);int prev = left;int cur = prev + 1;keyi = left;while (cur <= right) {cur 找小//while (cur < right && a[cur] >= a[keyi]) {//	cur++;//}//if (cur < right) {	//避免所有元素都大于 keyi//	prev++;//	Swap(&a[cur], &a[prev]);//}if (a[cur] < a[keyi]) {prev++;Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[keyi], &a[prev]);return prev;
}

非递归版本

考虑到递归会有栈溢出的风险,所以非递归版本,使用动态栈进行模拟

对栈有问题,请看之前的文章~

大致思想:见代码注释~

//非递归快排
void QuickSortNonR(int* a, int begin, int end) {//栈具有后进先出的性质//初始化一个动态栈Stack st;StackInit(&st);//将区间入栈StackPush(&st, end);StackPush(&st, begin);while (StackEmpty(&st)) {	//只要栈非空,子区间未分割完//从栈中取出一对区间int l = StackTop(&st);StackPop(&st);int r = StackTop(&st);StackPop(&st);//对这对区间分割int keyi = PartSort_3(a, l, r);//分割完之后,接着分割子区间// [l,keyi-1] keyi [keyi+1,r]//先让左右子区间入栈//避免区间不存在或者只有一个元素的情况if (keyi + 1 < r) {StackPush(&st, r);StackPush(&st, keyi + 1);}if (l < keyi - 1) {StackPush(&st, keyi - 1);StackPush(&st, l);}}StackDestroy(&st);
}

相关文章:

每日回顾:简单用C写 冒泡排序、快速排序

冒泡排序 冒泡排序&#xff08;Bubble Sort&#xff09;是一种简单的排序算法&#xff0c;它通过重复遍历要排序的数列&#xff0c;一次比较两个元素&#xff0c;如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行直到没有再需要交换&#xff0c;也就是说该数列已…...

前端_007_Axios库

文章目录 配置响应结构拦截器 引入&#xff1a; 官网&#xff1a; https://www.axios-http.cn/ 一句话简介&#xff1a;浏览器里基于XmlHttpRequests&#xff0c;node.js里基于http模块封装的网络请求库&#xff0c;使用非常方便 //通用例子axios({method:post,url: request…...

NAND FLASH 与 SPI FLASH

面试的时候再有HR针对从数据手册开始做&#xff0c;直接说明&#xff1a;例如RK3588等高速板设计板都有设计指导书&#xff0c;基本把对应的DDR等型号和布局规范都说明&#xff0c;或者DCDC电路直接给一个典型设计原理图&#xff0c;或者BMS更加经典&#xff0c;原理图给的是最…...

QTCreator打不开双击没反应

问题描述 双击后进程里显示有,当过几秒直接消失 解决 找到C\用户\AppData\Roaming\QtProject&#xff0c;删除目录下QtCreator.ini文件&#xff08;这会重置QtCreator的默认设置&#xff09;&#xff0c;再打开QtCreator时会自动生成对应于默认设置的QtCreator.ini文件&…...

vue npm run ...时 报错-系统找不到指定的路径

vue项目修改时&#xff0c;不知道那一步操作错误了&#xff0c;运行npm run …时报错 系统找不到指定的路径&#xff0c;对此进行记录一下&#xff01; 解决方法&#xff1a; 1、执行 npm install 命令&#xff0c;重新下载模块 2、根据下方提示执行 npm fund 查看详细信息 …...

54页可编辑PPT | 大型集团企业数据治理解决方案

这份PPT是关于大型集团企业数据治理的全面解决方案&#xff0c;它详细介绍了数据治理的背景、需求、管理范围、框架、解决思路&#xff0c;以及数据治理在实际操作中的关键步骤。内容涵盖了数据架构、数据质量、数据应用等方面的问题&#xff0c;并提出了数据资产透视、智能搜索…...

STM32嵌入式移植GmSSL库

前言 最近在做一个换电柜的项目&#xff0c;需要和云端平台对接json协议&#xff0c;由于服务端规定了&#xff0c;需要采用sm2 sm3 sm4用来加密。在嵌入式方面只能用北京大学的GmSSL了。 下载GmSSL 在https://github.com/guanzhi/GmSSL下载库 也可以通过git命令下载&#x…...

【mod分享】极品飞车10高清模组,,全新道路,全新建筑,高清植被,全新的道路围栏,全新的天空,画质直逼极品飞车20。支持光追

各位好&#xff0c;今天小编给大家带来一款新的高清重置魔改MOD&#xff0c;本次高清重置的游戏叫《极品飞车10卡本峡谷》。 《极品飞车10&#xff1a;卡本峡谷》该游戏可选择四个模式&#xff1a;生涯、快速比赛、挑战赛、多人连线游戏模式&#xff08;已不可用&#xff09;&…...

使用U-KAN训练自己的数据集 — 医疗影像分割

<U-KAN Makes Strong Backbone for Medical Image Segmentation and Generation> U-Net已成为各种视觉应用的基石,如图像分割和扩散概率模型。虽然通过整合变压器或mlp引入了许多创新设计和改进,但网络仍然局限于线性建模模式以及缺乏可解释性。为了应对这些挑战,受到…...

游戏盾在防御DDoS与CC攻击中的作用与实现

随着网络游戏的普及和发展&#xff0c;DDoS&#xff08;分布式拒绝服务&#xff09;攻击和CC&#xff08;Challenge Collapsar&#xff09;攻击成为了游戏服务器面临的主要威胁之一。游戏盾作为一种专门针对游戏行业设计的防御解决方案&#xff0c;能够在很大程度上减轻甚至消除…...

为什么说红帽认证(RHCE)是网络工程师的万金油证书?

在网络工程师圈子里&#xff0c;大家都知道考证的重要性&#xff0c;但面对一堆琳琅满目的认证&#xff0c;你可能会疑惑到底哪个证书含金量高、适用面广&#xff1f; 如果你问我&#xff0c;红帽认证&#xff08;RHCE&#xff09;绝对是当之无愧的“万金油”证书&#xff0c;…...

89.【C语言】编译和链接

1.翻译环境和运行环境总述 翻译环境:源代码被转换为机器码(又称为二进制指令)(包含编译和链接两个过程)依赖此环境 运行环境:可执行程序(Windows下的*.exe)到输出结果依赖此环境 2.翻译环境 翻译环境的解释 拆分为预处理(又称为预编译),编译和汇编三个过程 VS下的编译器:…...

优秀学员统计

题目描述 公司某部门软件教导团正在组织新员工每日打卡学习活动&#xff0c;他们开展这项学习活动已经一个月了&#xff0c;所以想统计下这个月优秀的打卡员工。每个员工会对应一个id&#xff0c;每天的打卡记录记录当天打卡员工的id集合&#xff0c;一共30天。 请你实现代码帮…...

电脑程序变化监控怎么设置?实时监控电脑程序变化的五大方法,手把手教会你!

​在现代办公和信息安全领域&#xff0c;实时监控电脑程序变化是一项至关重要的任务。 无论是企业内网安全、员工行为审计&#xff0c;还是个人电脑的隐私保护&#xff0c;了解并设置有效的监控方法都是必不可少的。 本文将详细介绍五种电脑程序变化监控的方法&#xff0c;帮助…...

2.1.3 编码和调制(下)

常用的调制方法 例题&#xff1a; 常用的QAM调制方案&#xff1a; QAM-16 即调制16种信号&#xff0c;1码元携带log2 164 bit数据 QAM-32 即调制32种信号&#xff0c;1码元携带log2 325 bit数据 QAM-64 即调制64种信号&#xff0c;1码元携带log2 646 bit数据 解题过程&…...

【网络安全渗透测试入门】之XSS漏洞检测、利用和防御机制XSS游戏(非常详细)收藏这一篇就够了!

一、前言 这是我给粉丝盆友们整理的网络安全渗透测试入门阶段XSS攻击基础教程。 本教程主要讲解XSS漏洞检测、利用和防御机制。 喜欢的朋友们&#xff0c;记得给我点赞支持和收藏一下&#xff0c;关注我&#xff0c;学习黑客技术。 Web的安全问题越来越严重&#xff0c;漏洞…...

[ComfyUI]Flux:超赞古风少女LORA,唯美江南水乡小桥流水轻舟江南美人

在数字艺术的世界里&#xff0c;ComfyUI的Flux技术再次展现了它的独特魅力。这次&#xff0c;它带来了一个全新的古风少女LORA模型&#xff0c;让用户能够轻松地创作出唯美江南水乡的场景&#xff0c;感受江南的韵味和小桥流水的诗意。 ComfyUI的Flux技术结合了先进的图像处理…...

从蚂蚁金服面试题窥探STW机制

背景 在Java虚拟机&#xff08;JVM&#xff09;中&#xff0c;垃圾回收&#xff08;GC&#xff09;是一个至关重要的机制&#xff0c;它负责自动管理内存的分配和释放。然而&#xff0c;垃圾回收过程并非没有代价&#xff0c;其中最为显著的一个影响就是STW&#xff08;Stop-T…...

【MySQL数据库】MySQL高级语句(SQL语句进阶版)

文章目录 SQL语句进阶版MySQL查询数据的过程一、连接与身份验证二、查询缓存&#xff08;MySQL 8.0之前版本&#xff09;三、查询解析与优化四、查询执行五、返回结果 MySQL语句准备环境创建 location 表并插入数据创建 store_info 表并插入数据查询示例 语句示例SELECTDISTINC…...

Milvus 到 TiDB 向量迁移实践

作者&#xff1a; caiyfc 原文来源&#xff1a; https://tidb.net/blog/e0035e5e 一、背景 我最近在研究使用向量数据库搭建RAG应用&#xff0c;并且已经使用 Milvus、Llama 3、Ollama、LangChain 搭建完成。最近通过活动获取了 TiDB Cloud Serverless 使用配额&#xff…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

leetcode_69.x的平方根

题目如下 &#xff1a; 看到题 &#xff0c;我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历&#xff0c;我们是整数的平方根&#xff0c;所以我们分两…...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...

【Redis】Redis从入门到实战:全面指南

Redis从入门到实战:全面指南 一、Redis简介 Redis(Remote Dictionary Server)是一个开源的、基于内存的键值存储系统,它可以用作数据库、缓存和消息代理。由Salvatore Sanfilippo于2009年开发,因其高性能、丰富的数据结构和广泛的语言支持而广受欢迎。 Redis核心特点:…...

[10-1]I2C通信协议 江协科技学习笔记(17个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17...

视觉slam--框架

视觉里程计的框架 传感器 VO--front end VO的缺点 后端--back end 后端对什么数据进行优化 利用什么数据进行优化的 后端是怎么进行优化的 回环检测 建图 建图是指构建地图的过程。 构建的地图是点云地图还是什么信息的地图&#xff1f; 建图并没有一个固定的形式和算法…...