归并排序

2020-04-19

字数统计: 1k字 | 阅读时长≈ 4分

简介

归并，就是将两个有序的数组归并成一个更大的有序数组。归并排序，就是要将一个数组排序，可以先递归地将它分成两半分别排序，然后将结果归并起来。
使用归并排序，能够保证任意长度为N的数组排序所需时间和NlogN成正比，主要缺点就是它所需额外空间和N成正比。

对于归并排序，一种非常直接的办法就是将两个不同的有序数组归并到第三个数组中，但是，当使用归并排序对一个大数组排序时，需要进行很多次归并，如果每次归并时都创建一个新数组来存储排序，会带来不必要的空间损耗和其他问题。因此，原地归并是一个非常需要的办法，但是实现起来比较复杂。

具体分析

动图演示

strategy

算法实现与分析

public class MergeSort{

	//归并排序所需的辅助数组
	private static Comparable[] aux;	

	public static void sort(Comparable[] a){
		aux = new Comparable[a.length];
		sort(a,0,a.length-1);
	}

	//对数组 a[lo,hi]范围进行排序
	private static void sort(Comparable[] a, int lo, int hi){
		//如果只有一个元素或者没有元素需要排序，直接返回
		if(lo>=hi){
			return ;
		}

		//取数组中点，以便于一分为二；
		int mid = lo + (hi-lo)/2;

		sort(a,lo,mid);		//将数组左半部分归并排序
		sort(a,mid+1,hi);	//将数组右半部分归并排序
		merge(a,lo,mid,hi);	//将数组有序的两部分进行归并
	}

	//对数组两部分进行归并
	private static void merge(Comparable[] a, int lo, int mid, int hi){
		//先复制一份a到辅助数组，以便于等下合并直接从辅助数组中取值放回原数组
		for(int k = lo; k <= hi; k++){
			aux[k] = a[k];
		}

		////合并 a[lo,mid]和a[mid+1,hi]到数组a;
		//由于数组两分，所以需要两个指针分别指向数组的首部；
		int i = lo, j = mid+1;
		for(int k = lo; k <= hi; k++){
			//如果数组左半部分已经全部放回，那么剩下直接把右半部分按序放到数组后面空余处即可
			if(i>mid){
				a[k] = aux[j];
			}
			//如果数组右半部分已经全部放回，那么把左半部分剩余部分直接放到数组后面空余处即可
			else if(j>hi){
				a[k] = aux[i];
			}
			else if(aux[i]<aux[j]){
				a[k] = aux[i];
				i++
			}else{
				a[k] = aux[j];
				j++;
			}
		}

	}
}

结论：

对于长度为N的任意数组，自顶向下的归并排序需要 1/2NlogN至NlogN次比较。
对于长度为N的人以数组，自顶向下的归并排序最多需要访问数组6NlgN次
- 每次归并最多需要访问数组6N次，2N次用来复制，2N次用来将排好序的元素移动回去，另外最多比较2N次

这里套用《算法4》中的证明过程：
假定C(N)为长度为N的数组进行归并排序时所需要的比较次数，有C(0)=C(1)=0，对于N>1，可以得到等式：
C(N) <= C(N/2)+C(N/2)+N
其中C(N/2)可以是数组左半部分排序或者右半部分排序所需要的比较次数，N是两部分进行归并时的比较次数。
还可以得到等式：
C(N) >= C(N/2)+C(N/2)+N/2
这里的N/2是当数组的两部分中某一部分所有元素都小于或者大于另一部分的所有元素时的比较次数；如 1 2 3 4与5 6 7 8进行归并，1与5比较，放回1，2与5比较，放回2，3与5比较，放回3，4与5比较，放回4，然后将5 6 7 8依次放回，这里就能看出仅当这种理想情况下，两个部分归并只需要N/2次比较。
假定N为2的幂次方，就可以从上面两个公式得出，C(N) = NlogN

参考

本文作者： xczll
本文链接： https://xczllgit.github.io/2020/04/19/algorithm/2020-04-19-mergeSort/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！