合并排序
合并排序(MERGE
SORT)是又一类不同的排序方法,合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。它的基本思想就是假
设数组A有N个元素,那么可以看成数组A是又N个有序的子序列组成,每个子序列的长度为1,然后再两两合并,得到了一个 N/2
个长度为2或1的有序子序列,再两两合并,如此重复,值得得到一个长度为N的有序数据序列为止,这种排序方法称为2—路合并排序。
例如数组A有7个数据,分别是: 49 38 65 97 76 13 27,那么采用归并排序算法的操作过程如图7所示:
初始值 [49] [38] [65] [97] [76] [13] [27]
看成由长度为1的7个子序列组成
第一次合并之后 [38 49] [65 97] [13 76] [27]
看成由长度为1或2的4个子序列组成
第二次合并之后 [38 49 65 97] [13 27 76]
看成由长度为4或3的2个子序列组成
第三次合并之后 [13 27 38 49 65 76 97]
图6 归并排序算法过程图
合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现,形式上较为简单,但实用性很差。
合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数
是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次,按照这一
X
规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X)。
*/
-
public
static
void
mergeSort(
int
[] array,
int
low,
int
height){
-
if
(low>=height)
return
;
-
int
mid = (low+height)/
2
;
-
mergeSort(array,low,mid);
-
mergeSort(array,mid+1
,height);
-
merge(array,low,mid,height);
-
}
-
-
public
static
void
merge(
int
[] array,
int
low,
int
mid,
int
height){
-
int
i,j,h,k;
-
int
[] temp =
new
int
[array.length];
-
i=low;
-
h=low;
-
j=mid+1
;
-
-
while
(h<=mid&&j<=height){
-
if
(array[h]<array[j]){
-
temp[i] = array[h];
-
h++;
-
}else
{
-
temp[i] = array[j];
-
j++;
-
}
-
i++;
-
}
-
-
if
(j>height){
-
for
(k=h;k<=mid;k++){
-
temp[i] = array[k];
-
i++;
-
}
-
}else
{
-
for
(k=j;k<=height;k++){
-
temp[i] = array[k];
-
i++;
-
}
-
}
-
for
(k=low;k<=height;k++){
-
array[k] = temp[k];
-
}
-
}
分享到:
相关推荐
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
归并排序-flash演 可自己输入数据..........
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
数据结构教学课件:第23讲 归并排序-基数排序.pdf
合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(DivideandConquer)的一个非常典型的应用。合并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,...
本程序实现了系统自动生成100万个随机浮点数,然后分别调用本程序采用分之策略实现的归并排序算法和系统STL中的Sort()方法,对其排序的时间进行比较。
java代码-归并排序-----
作业24-归并排序与基数排序.docx 作业24-归并排序与基数排序.docx ...作业24-归并排序与基数排序.docx作业24-归并排序与基数排序.docx作业24-归并排序与基数排序.docx作业24-归并排序与基数排序.docx
这是个算法设计,比较简单,但是可以实现.采用分治策略进行归并排序.
MATLAB实现《算法设计与分析》中的插入排序、二分归并排序、归并排序实验,其中包括.m文件和实验报告,安徽大学本科课程。
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
归并排序,比较高效的排序算法之一。这是一个例子,一个关于归并排序的例子。
排序-6-二路归并.cpp
算法-理论基础- 排序- 归并排序(包含源程序).rar