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

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语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍 一、快速排序非递归 快速排序非递归的定义 快速排序非递归&#xff0c;需要使用栈来实现。将左右下标分别push到栈中。在栈为…...

学生成绩管理系统(大一大作业)

功能 实现添加&#xff0c;排序&#xff0c;修改&#xff0c;保存等功能 库函数 #include<stdio.h> #include<stdlib.h> #include<windows.h> #include<string.h> 头文件 #define functioncreate(major) void major##compare(mana mn){\int i,j,s…...

数据结构:模拟栈

数据结构&#xff1a;模拟栈 题目描述参考代码 题目描述 输入样例 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 顺序表和链表的比较

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏&#xff0c;今后还会不断更新。&#x1f9d1;‍&#x1f4bb; 此外&#xff0c;《程序员必备技能》专栏和《程序员必备工具》专栏&#xff08;该专栏暂未开设&#xff09;日后会逐步更新&#xff0c;感兴趣的小伙伴可以点一下订阅…...

C++ : 模板初阶

标题&#xff1a;C : 模板初阶 水墨不写bug 正文开始&#xff1a; C语言的问题 &#xff1a; 写不完的swap函数 在学习C语言时&#xff0c;我们有一个经常使用的函数swap函数&#xff0c;它可以将两个对象的值交换。 我们通常这样实现它&#xff1a; void swap(int t1,int t2)…...

FFA-Net:用于单图像去雾的特征融合注意力网络

摘要 论文链接&#xff1a;https://arxiv.org/pdf/1911.07559v2 在这篇论文中&#xff0c;我们提出了一种端到端的特征融合注意力网络&#xff08;FFA-Net&#xff09;来直接恢复无雾图像。FFA-Net架构由三个关键组件组成&#xff1a; 一种新颖的特征注意力&#xff08;FA&…...

网工内推 | 联通公司,云计算售前,AWS认证优先

01 联通数字科技有限公司 &#x1f537;招聘岗位&#xff1a;云计算售前工程师 &#x1f537;职责描述&#xff1a; 1.了解私有云&#xff0c;公有云&#xff0c;混合云等云计算技术知识&#xff0c;了解云计算行业现状及发展趋势。 2.承担区域项目售前工作支持&#xff0c;为…...

[Redis]Zset类型

Zset有序集合相对于字符串、列表、哈希、集合来说会有一些陌生。 它保留了集合不能有重复成员的特点&#xff0c;但与集合不同的是&#xff0c;有序集合中的每个元素都有一个唯一的浮点类型的分数&#xff08;score&#xff09;与之关联&#xff0c;着使得有序集合中的元素是可…...

【云原生】Kubernetes----Ingress对外服务

目录 引言 一、K8S对外方式 &#xff08;一&#xff09;NodePort 1.作用 2.弊端 3.示例 &#xff08;二&#xff09;externalIPs 1.作用 2.弊端 3.示例 &#xff08;三&#xff09;LoadBalancer 1.作用 2.弊端 &#xff08;四&#xff09;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++课程学习】:类和对象(上)(类的基础详细讲解)

&#x1f381;个人主页&#xff1a;我们的五年 &#x1f50d;系列专栏&#xff1a;C课程学习 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 &#x1f35f;1.1类的引出&#xff1a; &#x1f35f;1.2类的结构&#xff1a; &#x1f35f;1.3类的…...

HTML 转义字符(escape characters)及其对应的符号(symbols)

以下是常见的 HTML 转义字符及其对应的符号&#xff0c;这些可以用于在 HTML 或 JSX 中避免解析错误和特殊字符的冲突&#xff1a; 空格 ( ): 或 引号: 单引号&#xff08;&#xff09;&#xff1a;&apos;、&lsquo;、、&rsquo;双引号&#xff08;"&#x…...

CPASSOC代码详解

加载环境 library("MASS") require(MASS) # Modern Applied Statistics with S&#xff0c;"S"指的是S语言&#xff0c;由贝尔实验室的约翰钱伯斯&#xff08;John Chambers&#xff09;等人开发。S语言是R语言的前身&#xff0c;许多R语言的语法和功能都…...

dirfuzz-web敏感目录文件扫描工具

dirfuzz介绍 dirfuzz是一款基于Python3的敏感目录文件扫描工具&#xff0c;借鉴了dirsearch的思路&#xff0c;扬长避短。在根据自身实战经验的基础上而编写的一款工具&#xff0c;经过断断续续几个月的测试、修改和完善。 项目地址&#xff1a;https://github.com/ssrc-c/di…...

计算机发展史 | 从起源到现代技术的演进

computer | Evolution from origins to modern technology 今天没有参考资料哈哈 PPT&#xff1a;&#xff08;评论区&#xff1f;&#xff09; 早期计算工具 算盘 -算盘是一种手动操作的计算辅助工具&#xff0c;起源于中国&#xff0c;迄今已有2600多年的历史&#xff0c;是…...

45-3 护网溯源 - 为什么要做溯源工作

官网:CVERC-国家计算机病毒应急处理中心 西工大遭网络攻击再曝细节!13名攻击者身份查明→ (baidu.com) 护网溯源是指通过技术手段追踪网络攻击的来源和行为,其重要性体现在以下几个方面: 安全防御:了解攻击源头可以帮助组织加强网络安全防御,及时采取措施防止攻击的再次…...

【JavaEE 进阶(二)】Spring MVC(下)

❣博主主页: 33的博客❣ ▶️文章专栏分类:JavaEE◀️ &#x1f69a;我的代码仓库: 33的代码仓库&#x1f69a; &#x1faf5;&#x1faf5;&#x1faf5;关注我带你了解更多进阶知识 目录 1.前言2.响应2.1返回静态界面2.2返回数据2.3返回HTML代码 3.综合练习3.1计算器3.2用户登…...

光波长 深入程度

UV深入程度&#xff08;UVC&#xff0c; UVB&#xff0c; UVA&#xff09;https://mp.weixin.qq.com/s?__bizMzkwNTM0Njk3MA&mid2247483934&idx1&sn92d1ba67ead404e7714af11ec0526786&chksmc0f868ebf78fe1fd0610493e6f49a5d90835a20a829a900746906cda12f2fa12…...

MySQL数据库常见工具的基础使用_1

在上一篇文章中提到了对MySQL数据库进行操作的一些常见工具 mysqlcheck mysqlcheck是一个用于数据库表的检查&#xff0c;修复&#xff0c;分析和优化的一个客户端程序 分析的作用是查看表的关键字分布,能够让sql生成正确的执行计划(支持InnoDB,MyISAM,NDB)检查的作用是检查…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...