归并排序是分治思想的一个很好的例子。它比希尔排序在时间复杂度上更优,为NlogN,并且属于稳定排序方法(稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的)。
自上而下的归并排序思想是,依赖于递归,逐级将待排序对象分割为较小的集合,直到这个集合只剩下一个元素,最后再归并每两个集合,排序的动作就发生在这个归并(merge)的时候。一分一合之间,集合就被排序了。
public class MergeSort {
private Comparable[] aux;
public void sort(Comparable[] a){
aux = new Comparable[a.length];
sort(a,0,a.length-1);
}
private void sort(Comparable[] a,int lo,int hi) {
if(hi<=lo) return;
int mid = lo + (hi - lo)/2;//将数组一分为二
sort(a,lo,mid);//分别对这两个子数组进行排序
sort(a,mid + 1,hi);
merge(a,lo,mid,hi);//合并两个已经排序的数组
}
private void merge(Comparable[] a,int lo,int mid,int hi){
int i = lo;
int j = mid + 1;
for(int k = lo;k<=hi;k++){//将待排序数组全部复制到临时数组中
aux[k] = a[k];
}
for(int k = lo;k<=hi;k++){//从临时数组中拿回到排序数组中
if(i>mid) a[k] = aux[j++];//左边数组已经没有元素可拿了,拿右边数组元素
else if(j>hi) a[k] = aux[i++];//右边数组已经没有元素可拿了,拿左边边数组元素
else if(less(aux[i],aux[j])) a[k] = aux[i++];//谁小拿谁
else a[k] = aux[j++];
}
}
private boolean less(Comparable a, Comparable b) {
return a.compareTo(b)<0;
}
public static void main(String[] args) {
int size = 3000000;
Integer[] a = RandomFactory.randomInt(size,40000);
MergeSort sort = new MergeSort();
//sort.show(a);
long t = System.currentTimeMillis();
sort.sort(a);
t = System.currentTimeMillis() -t;
//sort.show(a);
System.out.println("Insert sort");
System.out.println("time:" + t);
System.out.println("random data size : " + size);
}
private void show(Comparable[] a) {
int i = 0;
for(Comparable c : a){
System.out.print(c+" ");
i++;
if(i%20==0){
System.out.println();
}
}
System.out.println();
}
}
测试结果显示,同样是对300万测试数据进行排序,归并排序较希尔排序时间上有明显的优势:
Merge sort
time:2068
random data size : 3000000
Shell sort
time:7075
random data size : 3000000
分享到:
相关推荐
C++排序算法之归并排序源码
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
主要介绍了C语言实现排序算法之归并排序,对归并排序的原理及实现过程做了非常详细的解读,需要的朋友可以参考下
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
归并排序,两种实现方法,一种是递归实现,另一种是非递归实现……可直接在vc6.0平台上编译运行,并按要求输入,便可从小到大的顺序输出……
自己编写的基于java的快速排序和归并算法
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
根据算法导论实现的归并排序算法
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
C++实现希尔、快速、堆排序、归并排序算法,一些中文注释可能成乱码了,但是不影响代码执行。
本人自己写的一些排序算法,这是系列1归并排序算法实现,
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
采用c++描述了各种排序算法,包括选择排序 冒泡排序 插入排序 基数排序 快速排序 归并排序 。实验内容 1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、*基数排序、*快速排序、*归并排序。 3、*能够...
易语言归并排序算法源码,归并排序算法,归并排序,子程序_有序数组合并
本文件是7种常用排序算法的实现(C++),包括冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序以及快速排序。代码详细有注释且有测试用例。
从排序的基本概念讲起,详细讲解了插入排序、交换排序、选择排序、归并排序等排序算法的原理以及实现代码