归并排序——Java语言描述

发表于 | 分类于 | 阅读次数

归并排序 所谓“归并”，是将两个或两个以上的有序文件合并成一个新的有序文件。其中将两个有序表合并成一个有序表的归并排序称为2-路归并。

程序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.Arrays;

public class MergingSort {

	/**
	 * 2-路归并排序：将长度为n的待排序记录看作是一个含有n个长度为1的有序子表，把这些子表以次两两归并，
	 * 			 得到[n/2]个有序的子表；然后再把这[n/2]个有序子表进行两两归并，如此重复，
	 * 			 直到最后得到一个长度为n的有序子表为止。
	 * 空间复杂度为O(n)
	 * 时间复杂度为O(nlogn)
	 * 算法稳定性：2-路归并排序是一种稳定的排序算法
	 * */
	
	/* 两个有序列表的归并算法 */
	public static void Merge(int merge[],int temp[],int m,int n,int k) {
		int i,j;
		int len = n-m+1;		
		for(i=k+1,j=m; m<=k && i<=n; j++){	//将merg中的记录由小到大并入temp
			if(merge[m]<merge[i]){
				temp[j]=merge[m++];
			}
			else {
				temp[j] = merge[i++];
			}
		}
		for(; m<=k; j++){	////将剩余的merge[n...m]复制到temp
			temp[j] = merge[m++];
		}
		for(; i<=n; j++){  //将剩余的merge[i...n]复制到temp
			temp[j] = merge[i++];
		}
		
		for(i=0; i<len; i++){		//将temp复制到merge
			merge[n] = temp[n];
			n--;
		}
	}
	
	/* 2-路归并排序算法 */
	public static void MergeSort(int merge[],int temp[],int m, int n) {
		if(m<n){
			int k = (m+n)/2;
			MergeSort(merge, temp, m, k);		//左边
			MergeSort(merge, temp, k+1, n);		//右边
			Merge(merge, temp, m, n ,k);		//归并两个有序列表
		}
		
	}
	
	public static void MergeSort(int merge[]) {
		MergeSort(merge,new int[merge.length],0,merge.length-1);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int merge[] = {52,39,67,95,70,8,25,52,56,16};
		MergeSort(merge);
		System.out.println("归并后序列："+Arrays.toString(merge));
	}
}

测试结果

1
归并后序列：[8, 16, 25, 39, 52, 52, 56, 67, 70, 95]