排序算法(2)之归并排序——java实现

本文要讲的归并排序是继快速排序之后的又一常用排序算法，相似的是归并排序也是一种分治算法，因此，与快排一样，对于规模较大的问题，非常适用。

 

与快排相比，归并排序是稳定的，最重要的是其优点在于，其最差时间复杂度也是O(NlogN)。

归并排序是将两个（两个以上按两两处理）有序表合并成一个新的有序表。这里要强调下，待归并的两个数列必须是有序的。具体原因见算法。

 

算法思想：

1.首先将原数列，分解成左右两部分

2.分别对左右两部分，进行分解处理

3.再讲子部分合并成为一个有序数列

 

代码框架如下：

static void merge(int[] a,int begin ,int end){
	if(begin == end){//只有一个元素的时候，认为已经排好序，跳出递归
	    return;
	}
	if(begin<end){
		int mid = (begin + end)/2;
		//分解左半部分和右半部分
1.                merge(a,begin,mid);
2.		merge(a,mid+1,end);
                               
                //将分解处理之后的部分进行合并
3.		mergeAndSort(a,begin,mid,end);
	}
}

 如果对递归不是特别熟悉的话，可以结合这个例子，手动的画出递归栈

      ↓  begin                                           ↓ mid                                                                           ↓ end 

5

4

2

7

9

1

 

接下来的重点是merge：

比如说

a的左半部分是：1 3 8，赋值给left[]

a的右半部分是：2 4 5，赋值给right[]

为了方便对比，我们将left和right的最后加一个哨兵元素MAX，这样就不比对最后一个元素做特殊处理了。

static void mergeAndSort(int[] a,int begin,int mid,int end){
	int[] left = new int[mid - begin + 2]; //多留出一个哨兵位
	int[] right = new int[end - mid + 1];
	for(int i = begin ; i <= end; i++){
		if(i <= mid){
			left[i - begin] = a[i];
		}else{
			right[i - mid - 1] = a[i];
		}
	}
	left[mid - begin + 1] = Integer.MAX_VALUE;
	right[end - mid] = Integer.MAX_VALUE;
	int i = 0;
	int j = 0;
	int index = begin;
	while(index <= end){//按照顺序，将左右两部分归并
		a[index++] = left[i] < right[j] ? left[i++] : right[j++];		
	}
}

 

 

附录：

全部源代码为：

package sort;

import java.util.Arrays;

public class Merge {
	
	static void merge(int[] a,int begin ,int end){
		if(begin == end){
			return;
		}
		if(begin<end){
			int mid = (begin + end)/2;
			merge(a,begin,mid);
			merge(a,mid+1,end);
			mergeAndSort(a,begin,mid,end);
		}
	}
	
	static void mergeAndSort(int[] a,int begin,int mid,int end){
		int[] left = new int[mid - begin + 2]; 
		int[] right = new int[end - mid + 1];

		for(int i = begin ; i <= end; i++){
			if(i <= mid){
				left[i - begin] = a[i];
			}else{
				right[i - mid - 1] = a[i];
			}
		}
		left[mid - begin + 1] = Integer.MAX_VALUE;
		right[end - mid] = Integer.MAX_VALUE;
		int i = 0;
		int j = 0;
		int index = begin;
		while(index <= end){
			a[index++] = left[i] < right[j] ? left[i++] : right[j++];			
		}
	}
	
	public static void main(String[] args) {
		int[] a = {1,9,5,7,4,6,3,8,11,24};
		merge(a,0,a.length - 1);
		System.out.println(Arrays.toString(a));
		//打印结果为：[1, 3, 4, 5, 6, 7, 8, 9, 11, 24]

	}
	
}