未加星标

Java排序算法--归并排序(MergeSort)

字体大小 | |
[系统(linux) 所属分类 系统(linux) | 发布者 店小二04 | 时间 20160901 | 作者 红领巾 ] 0人收藏点击收藏

简介

归并排序以O(NlogN)最坏情形时间运行,而所使用的比较次数几乎是最优的。

这个算法中基本的操作是合并两个已排序的表。基本的合并算法是取两个输入数组A和B,一个输出数组C,以及3个计数器Actr、Bctr、Cctr,它们初始置于对应数组的开始端。A[Actr]和B[Bctr]中的较小者被拷贝到C中的下一个位置,相关的计数器向前推进一步。当两个输入表有一个用完的时候,则将另一个表中剩余部分拷贝到C中。

合并两个已排序的表的时间显然是线性的,因为最多进行N-1次比较,其中N是元素的总数。

算法描述:如果N=1,那么只有一个元素需要排序,否则,递归地前将半部分数据和后半部分数据各自归并排序,得到得到排序后的两部分数据,然后使用上面描述的合并算法再将这两部分合并到一起。

分治(divide-and-conquer)策略:它将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段解得的各答案修补在一起。

实现代码如下:

/**
* Internal method that makes recursive calls
* @param a an array of Comparable items
* @param tmpArray an array to place the merged result
* @param left the left-most index of the subarray
* @param right the right-most index of the subarray
*/
private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] a,AnyType[] tmpArray,int left,int right) {
if(left<right){
int center = (left+right)/2;
mergeSort(a,tmpArray,left,center);
mergeSort(a,tmpArray,center+1,right);
merge(a,tmpArray,left,center+1,right);
}
}

/**
* Mergesort algorithm
* @param a an array of Comparable items
*/
public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] a){
AnyType[] tmpArray = (AnyType[])new Comparable[a.length];
mergeSort(a,tmpArray,0,a.length-1);
}

/**
* Internal method that merges two sorted halves of a subarray
* @param a an array of Comparable items
* @param tmpArray an array to place the merged result
* @param leftPos the left-most index of the subarray
* @param rightPos the index of the start of the second half
* @param rightEnd the right-most index of the subarray
*/
private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] a,AnyType[] tmpArray,int leftPos,int rightPos,int rightEnd){
int leftEnd = rightPos -1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
//main loop
while(leftPos<=leftEnd && rightPos<=rightEnd){
if(a[leftPos].compareTo(a[rightPos])<=0){
tmpArray[tmpPos++] = a[leftPos++];
}else{
tmpArray[tmpPos++] = a[rightPos++];
}
}
//Copy rest of the first array
while(leftPos<=leftEnd){
tmpArray[tmpPos++] = a[leftPos++];
}
//Copy rest of the right array
while(rightPos<=rightEnd){
tmpArray[tmpPos++] = a[rightPos++];
}
//Copy tmpArray back
for(int i=0;i<numElements;i++,rightEnd--){
a[rightEnd] = tmpArray[rightEnd];
}
}

归并排序分析

与其它的O(NlogN)排序算法比较,归并排序的运行时间严重依赖于比较元素和在数组(以及临时数组)中移动元素的相对开销。这些开销是和语言相关的。

在Java中,当执行一次泛型排序(使用Comparator)时,进行一次元素比较可能是昂贵的(因为比较可能不容易被内嵌,从而动态调度的开销可能会减慢执行的速度),但是移动元素则是省时的(因为它们是引用的赋值,而不是庞大对象的拷贝)。它就是标准Java类库中泛型排序所使用的算法。在Java中,快速排序用作基本类型的标准库排序。

在C++的泛型排序中,如果对象庞大,那么拷贝对象可能需要很大开销,而由于编译器具有主动执行内嵌优化的能力,因此比较对象常常是相对省时的。C++类库中通常使用快速排序(Quicksort)。

本文地址:http://www.linuxidc.com/Linux/2016-09/135311.htm


Java排序算法--归并排序(MergeSort)

本文系统(linux)相关术语:linux系统 鸟哥的linux私房菜 linux命令大全 linux操作系统

主题: 算法JavaC++编译器Linux数据
分页:12
转载请注明
本文标题:Java排序算法--归并排序(MergeSort)
本站链接:http://www.codesec.net/view/483475.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 系统(linux) | 评论(0) | 阅读(22)