合并排序(归并排序)
合并排序是利用分治法的算法思想来解决排序问题的。
分治法:将原问题划分成n个规模较小而结构与原问题相似的子问题,递归的解决这些子问题,然后将结果合并。
基本思想:将序列分为两个子序列,并对两个子序列分别排序,之后将已排序子序列合并,即为排序结果,其中两个子序列的 排序也按照分成更小的子序列,直至分解到单个元素,即为已排序子序列,然后合并。
算法描述:
合并算法:
%将数组中两个已排序部分合并为一个
%数组,从而得到已排序的数组A
function A = my_merge(A,p,q,r)
%n1,n2为两个已排序的数组长度。
n1 = q - p +1;
n2 = r - q;
L = zeros(1,n1);
R = zeros(1,n2);
%将两个已排序部分分别复制到L,R
for i = 1:1:n1
L(i) = A(p+i-1);
end
for j = 1:1:n2
R(j) = A(q+j);
end
%问题转化为将L,R两个已排序数组,合并到数组A中。
%引进“哨兵”,简化代码
L(n1 + 1) = 500;
R(n2 + 1) = 500;
%每一次一定会加入元素,而且直至加入r-p+1个元素
%所以仅需一次循环
i = 1;
j = 1;
for k = p:1:r
if L(i) < R(j)
A(k) = L(i);
i = i+1;
else
A(k) = R(j);
j = j+1;
end
end
排序:
%合并排序A,从下标p到r
function A = my_merge_sort(A,p,r)
%如果p小于r,将数组分为两部分
%分别对各个部分调用排序函数,
%最后合并
if p < r
q = floor((r + p)/2);
my_merge_sort(A,p,q); %排序前半部分
my_merge_sort(A,q+1,r); %排序后半部分
my_merge(A,p,q,r); %合并
end
end
时间复杂度:o(n*logn)
分享到:
相关推荐
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
编写选择排序,插入排序,自顶向上合并排序,合并排序,快速排序,理解各排序算法的实现原理,加深对排序算法的理解。
c++实现的合并排序算法 用递归和非递归两种方式实现的
归并排序C语言实现
单链表的创建,排序,归并,插入删除定位和获得元素,计算元素个数,打印链表
基于visual studio2010,的程序开发,...............................................................................................
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 ...(包括输入格式、算法、输出格式) ...(除了截图外,实验结果还用图表进行了分析) ...
合并排序的C++实现方法。使用递归方法实现。要求用户输入n个整数,程序输出排序结果
合并排序(MERGE SORT)是又一类不同的排序方法,合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。它的基本思想就是假设数组A有N个元素,那么可以看成数组A是又N个...
一年前做的排序动画,归并排序动画一直未完成,今天完成了,与大家共享
算法设计,给出归并排序的C++实现代码,并利用给随机数方式求运行时间
一个算法设计与分析的实验报告,比较归并排序与快速排序的时间差异,这里采用在一个java程序中对随机生成的任意个数分别进行两种方法的排序并记录各自的时间,最后得出结论。 本实验报告附代码以及详细解释
C++ 将产生的随机数存入文件中,使用冒泡、快速、归并、希尔排序并计算排序时间,将排序时间存入excel中
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待...
1、 掌握直接插入排序、折半插入排序、冒泡排序、快速排序和归并排序等排序算 法的思想。 2、 实现直接插入排序、折半插入排序、冒泡排序、快速排序和归并排序等排序算 法的编程应用。 二、 问题描述 实现数据的折半...
它的基本思想是:将待排序的数列分成两个小的数列,先对两个子集进行排序,然后进行两个有序子集的合并,形成... 设归并排序的当前区间是R[low..high],分治法的三个步骤是: ①分解:将当前区间一分为二,即求分裂点
根号n段归并排序算法的C++代码实现: 1.合并【根号n向下取整】段子数组,使用了自底向上的两两合并策略。 2.算法的总体时间复杂度为nlogn 3.带有详细注释
合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(DivideandConquer)的一个非常典型的应用。合并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序...合并排序也叫归并排序。
归并排序过程的前半部分,过程示意图见下,从图中可见,步骤1,2,3,4一直分割区间,等到步骤5时,左右区间长度都为1,此时发生一次归并,结果再与另一个区间长度为1的归并,即步骤6;步骤7分割,步骤8归并,步骤9...
根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导