排序----归并排序

上一篇:希尔排序

归并排序的特点:

  • (优点):能够保证将任意长度为N的数组排序所需时间和NlogN成正比。
  • (缺点):所需额外空间与N成正比。

归并排序是算法设计中分治思想的典型应用。

原地归并方法:

public static void merge(Comparable[] a,int lo,int mid,int hi){
	//原地归并方法
	int i=lo,j=mid+1;
	for(int k =lo;k<=hi;k++)//将a[]复制到aux[]
		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[j],aux[i]))    a[k] = aux[j++];//右边当前元素<左边当前元素(取右边元素)
		else                            a[k] = aux[i++];//右边当前元素>左边当前元素(取左边元素)
}
  • 对于长度为N的任意数组,自顶向下和自底向上的归并排序需要1/2*NlgN至NlgN次比较。
  • 对于长度为N的任意数组,自顶向下和自底向上的归并排序最多访问数组6*NlgN次。
  • 没有任何基于比较的算法能够保证使用少于lg(N!)~NlgN次比较将长度为N的数组排序。
  • 归并排序是一种渐进最优的基于比较排序的算法。

有了归并方法,自顶向下的归并排序很容易实现(分治思想):

public class Merge {
	private static Comparable[] aux;    //归并方法需要的辅助数组
	public static void sort(Comparable[] a){
		aux = new Comparable[a.length];
		sort(a,0,a.length-1);
	}
	public static 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);//归并
	}
	//less()、exch()、isSorted()、main()方法见“排序算法模板”
}

可以通过一些改进大幅缩短归并排序的运行时间,例如:

  • 对小规模子数组使用插入排序。
  • 测试数组是否已经有序。
  • 不将元素复制到辅助数组。

自底向上的归并排序:

public static void sort(Comparable[] a){
		int N = a.length();
		aux = new Comparable[N];
		for(int sz = 1;sz<N;sz = sz+sz)    //sz子数组的大小
			for(int lo=0;lo<N-sz;lo+=sz+sz)    //lo:子数组索引
				merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1, N-1));
}

自底向上的归并排序算法适合用链表组织的数据。

算法改动: 快速归并:按降序将a[]的后半部分复制到aux[],然后将其归并回a[],这样可以去掉循环中检测某半边是否用尽的代码。

次线性的额外空间:用大小M将数组分为N/M块,可以实现算法使需要的额外空间减少到max(M,N/M):

  1. 每个块用选择排序排序
  2. 块之间归并排序排序

下一篇:快速排序

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

字符串展开(递归)- HDU 1274

常用纱线的品种一般不会超过25种,分别可以用小写字母表示不同的纱线,例如:abc表示三根纱线的排列;重复可以用数字和括号表示,例如:2(abc)表示abcabc...

9320
来自专栏PPV课数据科学社区

数据结构常见的八大排序算法

前言 八大排序,三大查找是《数据结构》当中非常基础的知识点,在这里为了复习顺带总结了一下常见的八种排序算法。 常见的八大排序算法,他们之间关系如下: 他们的性能...

514110
来自专栏Python爱好者

Java基础笔记02

20520
来自专栏jeremy的技术点滴

排序算法python实现

38890
来自专栏较真的前端

关于数字的前端面试题

41360
来自专栏HTML5学堂

操作符与数据类型转换

上一期堡堡给大家讲解了关于JS的基础语法,虽然是一些非常基础的知识,但是它对大家的后期学习奠定了一定的基础。知识像一张网,基础越扎实,网住的鱼就越多,要告诉大家...

31880
来自专栏人工智能LeadAI

为什么算法容易忘记之插入排序

在学习常用的排序算法时,常有这样的感觉,一看就懂,过眼就忘。原因在于没有将排序的基本思想与代码中各个循环控制变量的意义联系起来进行理解记忆。 插入排序 首先,我...

35750
来自专栏诸葛青云的专栏

C语言入门基础学习函数?来看我就告诉你!

在前面我们已经讲过了一些简单的函数,如程序的主函数main()、标准输出函数printf()。在C语言中,大多数功能都是依靠函数来实现的。But,你知道什么是函...

14330
来自专栏逆向技术

计算机基础知识_进制转化

          进制转化 一.任何一个进制转化为10进制的方式 156的十进制可以看做1*10^2 + 5*10^1  +   6*10^0 首先我们看一下...

22900
来自专栏编舟记

Monad

什么是函数(Function)? 函数表达的映射关系在类型上体现在特定类型(proper type)之间的映射。

8550

扫码关注云+社区

领取腾讯云代金券