×
文章路径: Java > 算法 > 排序

合并排序MergeSort

发表于3年前(Dec 24, 2014 9:57:55 AM)  阅读 467  评论 0

分类: Java 算法 排序

标签: sort 排序 mergesort 合并排序 递归

合并排序是分治法的典型应用,就是我们常说的递归。合并排序是将两个已经排好序的数组合并成一个有序数组的过程,所以只需保证子数组有序,那么合并出来的数组也是有序的,那剩下的问题就是如何递归地对子数组进行排序。

package sort;

/**
 * 合并排序
 * @author lihui
 *
 */
public class MergeSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		int[] a = {1,3,4,2,5,7};
		int[] a = {5,3,1,1,3,0,2};
		sorted(a, 0,a.length-1);
		for(int i=0;i<a.length;i++) {
			System.out.println(a[i]);
		}

	}

	/**
	 * 将数组分为两半,分别排序
	 * @param a 要排序的数组
	 * @param p 要排序的开始索引
	 * @param r 要排序的结束索引
	 */
	public static void sorted(int[] a, int p, int r) {
		if(p<r) {
			int q = (p+r)/2;
			sorted(a, p, q);
			sorted(a, q+1, r);
			merge(a, p, q, r);
		}
	}

	/**
	 * 合并两个数组
	 * @param a 要合并的数组(要合并的两个数组的元素都在这个数组内)
	 * @param p 第一个数组的开始索引
	 * @param q 第一个数组结束的索引
	 * @param r 第二个数组结束的索引
	 * p<=q<r
	 */
	public static void merge(int[] a, int p, int q, int r) {
		//两个数组的长度
		int len1 = q-p+1;
		int len2 = r-q;
		//复制两个数组
		int[] a1 = new int[len1];
		int[] a2 = new int[len2];
		for(int i=0;i<len1;i++) {
			a1[i] = a[i+p];
		}
		for(int i=0;i<len2;i++) {
			a2[i] = a[i+q+1];
		}
		//从第一个数组取出的个数
		int i = 0;
		//从第二个数组取出的个数
		int j = 0;
		//从a1跟a2两个数组中各取当前第一个元素出来,比较大小,填充到a中
		while(i<=len1&&j<=len2) {
			//如果两个数组都已取玩,则排序完成
			if(i==len1&&j==len2) {
				break;
			}
			//如果第一个数组已经取玩,直接取第二个数组的元素
			if(i==len1) {
				a[p+i+j] = a2[j];
				j++;
				continue;
			}
			//如果第二个数组已经取玩,直接取第一个数组的元素
			if(j==len2) {
				a[p+i+j] = a1[i];
				i++;
				continue;
			}
			if(a1[i]<=a2[j]) {
				a[p+i+j] = a1[i];
				i++;
			} else {
				a[p+i+j] = a2[j];
				j++;
			}
		}
	}

}
合并排序是不能在原数组上实现的,他的时间复杂度为O(nlog n)。在上面的代码中,核心算法是merge合并算法。在该算法的实现中,对要合并的目标数组进行了拷贝,然后替换源数组的值,这样的话可读性较好,但实际上也是一件影响效率的工作。参考网上其它的算法,一般是返回一个新的排序数组,各中优略请读者自己把握。

发表评论