C#递归算法之归并排序
作者:张玉彬 发布时间:2023-01-01 14:49:36
归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为:
1)划分子表
2)合并半子表
首先我们来讨论归并算法,归并算法将一系列数据放到一个向量中,索引范围为[first,last],这个序列由两个排好序的子表构成,以索引终点(mid)为分界线,以下面一个序列为例
7,10,19,25,12,17,21,30,48
这样的一个序列中,分为两个子序列 7,10,19,25 和 12,17,21,30,48,如下图所示:
再使用归并算法的时候的步骤如下:
第一步:比较v[indexA]=7和v[indexB]=12,将较小的v[indexA]取出来放到临时向量tempArray中,然后indexA加1
第二步:比较v[indexA]=10和v[indexB]=12,将较小的10放到临时变量tempArray中,然后indexA++;
第三步:比较v[indexA]=19与v[indexB]=12,将较小的12存放到临时变量tempArray中,然后indexB++;
第四步到第七步:按照以上规则,进行比对和存储,得到如下结果:
最后一步:将子表b中剩余项添加到临时向量tempArray中
然后将临时变量中的值按照索引位置,拷贝回向量v中,就完成了对向量v的归并排序
算法函数为:
public void Merger(int[] v, int first, int mid, int last)
{
Queue<int> tempV = new Queue<int>();
int indexA, indexB;
//设置indexA,并扫描subArray1 [first,mid]
//设置indexB,并扫描subArray2 [mid,last]
indexA = first;
indexB = mid;
//在没有比较完两个子标的情况下,比较 v[indexA]和v[indexB]
//将其中小的放到临时变量tempV中
while (indexA < mid && indexB < last)
{
if (v[indexA] < v[indexB])
{
tempV.Enqueue(v[indexA]);
indexA++;
}
else
{
tempV.Enqueue(v[indexB]);
indexB++;
}
}
//复制没有比较完子表中的元素
while (indexA < mid)
{
tempV.Enqueue(v[indexA]);
indexA++;
}
while (indexB < last)
{
tempV.Enqueue(v[indexB]);
indexB++;
}
int index = 0;
while (tempV.Count > 0)
{
v[first+index] = tempV.Dequeue();
index++;
}
}
实现归并排序;归并排序算法分为两步,第一步:先将原来的数据表分成排好序的子表,然后调用 Merger 对子表进行归并,使之成为有序表,例如有如下向量:
25,10,7,19,3,48,12,17,56,30,21
对此序列进行归并排序的步骤为:
归并算法函数为
public void MergerSort(int[] v, int first, int last)
{
if (first + 1 < last)
{
int mid = (first + last) / 2;
MergerSort(v, first, mid);
MergerSort(v, mid, last);
Merger(v, first, mid, last);
}
}
归并算法的划分子表和归并子表与原数据序列次序无关,因此算法的最坏情况,最坏情况和平均情况时间复杂度是一样的
下面是归并算法的函数调用图
示例程序:http://xiazai.jb51.net/201606/yuanma/MergerSort(jb51.net).rar
猜你喜欢
- 问题现象:HTTP Status 403-Invalid CSRF Token 'null' was found on th
- 三种定义数组的格式如下:int[] arr1=new int[10];int[] arr2={1,2,3,6};int[] arr3=new
- 本文实例为大家分享了java实现人机猜拳游戏的具体代码,供大家参考,具体内容如下完成人机猜拳互动游戏的开发,用户通过控制台输入实现出拳,电脑
- 这篇文章主要介绍了Spring boot整合log4j2过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值
- 欢迎访问我的GitHub这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demo
- 前言本文简单介绍了设计模式的一种——职责链模式 一、职责链模式的定义与特点定义:为了避免请求发送者与多个请求处理者耦合在一起,于是
- 目前系统集成短信似乎是必不可少的部分,由于各种云平台都提供了不同的短信通道,这里我们增加多租户多通道的短信验证码,并增加配置项,使系统可以支
- 一.瀑布模型瀑布模型严格遵循软件生命周期各阶段的固定顺序:计划、分析、设计、编程、训试和维护,上一阶段完成后才能进入到下一阶段, 整个模型就
- 每种编程语言都有自己操作内存中元素的方式,例如在 C 和 C++ 里是通过指针,而在 Java 中则是通过“引用”。在 JDK.1.2 之后
- 1.下载安装OpenCVhttps://opencv.org/releases/选择合适的平台安装包下载,然后双击安装,也就是解压的过程。这
- 本文实例为大家分享了Java实现带图形界面聊天程序的具体代码,供大家参考,具体内容如下ServerDemo01.javaimport jav
- 本文实例讲述了Java实现的日期处理类。分享给大家供大家参考,具体如下:开发中常常要使用日期,先小结如下,以备后用。import java.
- 一、思路1.定义一个toFind变量来传入要查找的元素2.遍历整个顺序表并判定当前下标的元素等不等于toFind3.如果等于就返回一个tru
- 01.点明观点C#中,非托管资源使用之后必须释放,而using()是使用非托管资源的最佳方式,可以确保资源在代码块结束之后被正确释放,并且代
- 第三章 字符串,比较器和过滤器JDK引入的一些方法对写出函数式风格的代码很有帮助。JDK库里的一些的类和接口我们已经用得非常熟悉了,比如说S
- 前端控制器是整个MVC框架中最为核心的一块,它主要用来拦截符合要求的外部请求,并把请求分发到不同的控制器去处理,根据控制器处理后的结果,生成
- 本文实例为大家分享了java实现双色球抽奖的具体代码,供大家参考,具体内容如下实现双色球先考虑整体思路:1.随机生成7位数的数组为大奖号码(
- 在我的工作经验中,在C#语言本身的学习上花了大量的时间,积累了一些经验,一些是在学习和工作中遇到的问题和解决办法分享出来,希望大家也能有收获
- 中文乱码问题真的是一个很棘手的问题,特别是从前台传到后台之后,都不知道问题出在哪里了。现在分享解决javaWEB中前后台中文乱码问题的3种方
- springcloud-gateway集成knife4j环境信息环境信息spring-boot:2.6.3spring-cloud-alib