C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍
文章目录
- 前言
- 一、快速排序非递归
- 二、归并排序
- 五、归并排序非递归
- 总结
前言
C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍
一、快速排序非递归
快速排序非递归的定义
- 快速排序非递归,需要使用栈来实现。
- 将左右下标分别push到栈中。
- 在栈为空之前,循环获取区间的中间值下标并同时将左右区间排序。
- 判断若中间值下标(keyi) + 1小于end,则将此区间push到栈中。
- 若begin 小于 中间值下标(keyi),则将此区间push到栈中。
- 循环直到栈为空。
int PartSort3(int* a, int left, int right)
{int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){/*if (a[cur] < key){prev++;Swap(&a[cur], &a[prev]);}cur++;*/if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[cur], &a[prev]);cur++;}Swap(&a[prev], &a[keyi]);return prev;
}// 快速排序非递归
void QuickSortNonR(int* a, int left, int right)
{int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort3(a, begin, end);if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi - 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}
- 其中PartSort3函数是快速排序快慢指针的单趟排序。
快速排序非递归测试
void TestQuickSortNonR()
{int a[] = { 9, 7, 6 ,4 ,8 ,3 ,5 ,1 ,2, 0 };PrintArray(a, sizeof(a) / sizeof(a[0]));QuickSortNonR(a, 0, sizeof(a) / sizeof(a[0]) - 1);PrintArray(a, sizeof(a) / sizeof(a[0]));
}
效果如下:

二、归并排序
归并排序定义
- 直接将区间拆分成左右区间。
- 左右区间分别递归直到单个数字,并在返回后归并左右区间到一个临时的数组中。
- 然后将临时数组中的数字memcpy拷贝到原数组中。
// 归并排序
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right)return;int midi = left + (right - left) / 2;int begin1 = left, end1 = midi;int begin2 = midi + 1, end2 = right;_MergeSort(a, begin1, end1, tmp);_MergeSort(a, begin2, end2, tmp);int i = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort malloc");return;}int left = 0;int right = n - 1;_MergeSort(a, left, right, tmp);free(tmp);
}
归并排序测试
void TestMergeSort()
{int a[] = { 9, 7, 6 , 6, 4,4 ,8 ,3 ,5 ,1 ,2, 0, 5 };PrintArray(a, sizeof(a) / sizeof(a[0]));MergeSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}
效果如下:

五、归并排序非递归
归并排序非递归定义
- 归并一部分拷贝一部分
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;while (gap < n){int i = 0;for (i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);tmp = NULL;
}
归并排序非递归测试
void TestMergeSortNonR()
{int a[] = { 9, 7, 6 , 6, 4,4 ,8 ,3 ,5 ,1 ,2, 0, 5 };PrintArray(a, sizeof(a) / sizeof(a[0]));MergeSortNonR(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}
效果如下:

总结
C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍
相关文章:
C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍
文章目录 前言一、快速排序非递归二、归并排序五、归并排序非递归总结 前言 C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍 一、快速排序非递归 快速排序非递归的定义 快速排序非递归,需要使用栈来实现。将左右下标分别push到栈中。在栈为…...
学生成绩管理系统(大一大作业)
功能 实现添加,排序,修改,保存等功能 库函数 #include<stdio.h> #include<stdlib.h> #include<windows.h> #include<string.h> 头文件 #define functioncreate(major) void major##compare(mana mn){\int i,j,s…...
数据结构:模拟栈
数据结构:模拟栈 题目描述参考代码 题目描述 输入样例 10 push 5 query push 6 pop query pop empty push 4 query empty输出样例 5 5 YES 4 NO参考代码 #include <iostream>using namespace std;const int N 1000010;int m, x; int q[N]; string op; int…...
02-2.3.6 顺序表和链表的比较
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏,今后还会不断更新。🧑💻 此外,《程序员必备技能》专栏和《程序员必备工具》专栏(该专栏暂未开设)日后会逐步更新,感兴趣的小伙伴可以点一下订阅…...
C++ : 模板初阶
标题:C : 模板初阶 水墨不写bug 正文开始: C语言的问题 : 写不完的swap函数 在学习C语言时,我们有一个经常使用的函数swap函数,它可以将两个对象的值交换。 我们通常这样实现它: void swap(int t1,int t2)…...
FFA-Net:用于单图像去雾的特征融合注意力网络
摘要 论文链接:https://arxiv.org/pdf/1911.07559v2 在这篇论文中,我们提出了一种端到端的特征融合注意力网络(FFA-Net)来直接恢复无雾图像。FFA-Net架构由三个关键组件组成: 一种新颖的特征注意力(FA&…...
网工内推 | 联通公司,云计算售前,AWS认证优先
01 联通数字科技有限公司 🔷招聘岗位:云计算售前工程师 🔷职责描述: 1.了解私有云,公有云,混合云等云计算技术知识,了解云计算行业现状及发展趋势。 2.承担区域项目售前工作支持,为…...
[Redis]Zset类型
Zset有序集合相对于字符串、列表、哈希、集合来说会有一些陌生。 它保留了集合不能有重复成员的特点,但与集合不同的是,有序集合中的每个元素都有一个唯一的浮点类型的分数(score)与之关联,着使得有序集合中的元素是可…...
【云原生】Kubernetes----Ingress对外服务
目录 引言 一、K8S对外方式 (一)NodePort 1.作用 2.弊端 3.示例 (二)externalIPs 1.作用 2.弊端 3.示例 (三)LoadBalancer 1.作用 2.弊端 (四)Ingress 二、Ingress的…...
项目管理之maven svn
管理jar包之间依赖关系 编译、打包、清理、测试等一系列构建工具 一、Maven的标志 1、每一个maven工程都有一个pom.xml maven项目坐标 <groupId>com.aaa</groupId>//项目路径 <artifactId>web</artifactId>项目名称 <version>0.0.1-SNAPS…...
Redis篇 list类型在Redis中的命令操作
list在redis基本的命令 一.基本命令1.lpush和range2.lpushx rpushx3.lpop rpop4.lindex linsert llen5.lrem6.ltrim lset7.blpop brpop 一.基本命令 list在redis中相当于数组或者顺序表. 1.lpush和range 2.lpushx rpushx 3.lpop rpop 4.lindex linsert llen 如果要插入的列表中…...
【C++课程学习】:类和对象(上)(类的基础详细讲解)
🎁个人主页:我们的五年 🔍系列专栏:C课程学习 🎉欢迎大家点赞👍评论📝收藏⭐文章 目录 🍟1.1类的引出: 🍟1.2类的结构: 🍟1.3类的…...
HTML 转义字符(escape characters)及其对应的符号(symbols)
以下是常见的 HTML 转义字符及其对应的符号,这些可以用于在 HTML 或 JSX 中避免解析错误和特殊字符的冲突: 空格 ( ): 或 引号: 单引号():'、‘、、’双引号("&#x…...
CPASSOC代码详解
加载环境 library("MASS") require(MASS) # Modern Applied Statistics with S,"S"指的是S语言,由贝尔实验室的约翰钱伯斯(John Chambers)等人开发。S语言是R语言的前身,许多R语言的语法和功能都…...
dirfuzz-web敏感目录文件扫描工具
dirfuzz介绍 dirfuzz是一款基于Python3的敏感目录文件扫描工具,借鉴了dirsearch的思路,扬长避短。在根据自身实战经验的基础上而编写的一款工具,经过断断续续几个月的测试、修改和完善。 项目地址:https://github.com/ssrc-c/di…...
计算机发展史 | 从起源到现代技术的演进
computer | Evolution from origins to modern technology 今天没有参考资料哈哈 PPT:(评论区?) 早期计算工具 算盘 -算盘是一种手动操作的计算辅助工具,起源于中国,迄今已有2600多年的历史,是…...
45-3 护网溯源 - 为什么要做溯源工作
官网:CVERC-国家计算机病毒应急处理中心 西工大遭网络攻击再曝细节!13名攻击者身份查明→ (baidu.com) 护网溯源是指通过技术手段追踪网络攻击的来源和行为,其重要性体现在以下几个方面: 安全防御:了解攻击源头可以帮助组织加强网络安全防御,及时采取措施防止攻击的再次…...
【JavaEE 进阶(二)】Spring MVC(下)
❣博主主页: 33的博客❣ ▶️文章专栏分类:JavaEE◀️ 🚚我的代码仓库: 33的代码仓库🚚 🫵🫵🫵关注我带你了解更多进阶知识 目录 1.前言2.响应2.1返回静态界面2.2返回数据2.3返回HTML代码 3.综合练习3.1计算器3.2用户登…...
光波长 深入程度
UV深入程度(UVC, UVB, UVA)https://mp.weixin.qq.com/s?__bizMzkwNTM0Njk3MA&mid2247483934&idx1&sn92d1ba67ead404e7714af11ec0526786&chksmc0f868ebf78fe1fd0610493e6f49a5d90835a20a829a900746906cda12f2fa12…...
MySQL数据库常见工具的基础使用_1
在上一篇文章中提到了对MySQL数据库进行操作的一些常见工具 mysqlcheck mysqlcheck是一个用于数据库表的检查,修复,分析和优化的一个客户端程序 分析的作用是查看表的关键字分布,能够让sql生成正确的执行计划(支持InnoDB,MyISAM,NDB)检查的作用是检查…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
