Fork me on GitHub

算法-归并排序算法

发表于 | 分类于 | 阅读次数
面试算法之----归并排序算法（摘自数据结构与算法经典问题解析262页问题10.9 ）

归并排序算法是分治算法技术的一个实例。

插入排序、交换排序、和选择排序这三类排序算法都是讲无序的记录序列按关键字的带下排成一个有序序列。而归并排序则是将两个或者以上的有序序列合并成为一个有序序列的过程。将两个有序序列合并（归并）成一个有序序列称为二路归并。将N个有序序列合并（归并）成一个有序序列称为N路归并。

时间复杂度：

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O（n）
    重要提示：
  • 归并是把两个已排序文件合并成一个更大的已排序文件的过程。
  • 归并排序是快速排序的补充。
  • 归并排序以连续的方式访问数据。
  • 归并排序适用于链表排序。
  • 归并排序对输入的初始次序不敏感。
  • 快排是从最大子文件开始并以最小子文件结束，因此需要栈结构。归并排序是以最小子文件开始而以最大子文件结束，因此不需要栈。
  • 归并算法是稳定的算法。

基本思想：

归并排序分为两部分，拆分与合并。下面以二路归并为例：

  • 将长度为n的无序表对半分成两个无序子表，并对每一个无序子表继续进行对半拆分为两个子表的工作，直到每一个子表的长度为1，形成长度为1的有序子表（表长为1时为有序子表）。

  • 开始第一趟二路归并，即将第1个表同第2个表归并，第3个表同第4个表归并·······若最后仅剩最后一个表，则不参加归并。这样得到的[n/2] 个长度为2（最后一个表的长度可能为1） 的有序表。

  • 进行第二趟二路归并，即将第一趟得到的有序表继续进行两两归并，从而得到[n/4] 个长度为4（最后一个表的长度可能小于4） 的有序表。

  • 以此类推，直到第[logn]趟归并完成，就得到了长度为n的有序表。

对上面的过程我们可以总结为这样一种思想：

递归拆分，两两合并。

算法实现（java）：

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
	/**
	* 对两个数组合并
	*/
	public static void MergeArray(int[] A,int first,int last,int mid,int[] temp){
		int k=0;
		int i=first;
		int j=mid+1;
		while(i<=mid && j<=last){
			
			if(A[i]<=A[j]){
				temp[k++]=A[i++];
			}else{
				temp[k++]=A[j++];
			}
		}
			
		while(i<=mid){
				temp[k++]=A[i++];
			}
		while(j<=last){
				temp[k++]=A[j++];
			}
		for(int l=0;l<k;l++){
			A[first+l]=temp[l];
		}	
}
	
	public static void MergeSort(int[] A,int first,int last,int[] temp){
		int mid=(first+last)/2;
		if(first<last){
			//递归对左右两边折半，最深一层左右各剩下一个元素
			MergeSort(A, first, mid, temp);   
			MergeSort(A, mid+1, last, temp);
			MergeArray(A, first, last, mid, temp);
		}
	}

测试程序：

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A=new int[]{1,4,2,8,5,9,477,25,1};
		int[] temp=new int[A.length];
		long time=System.nanoTime();
		MergeSort(A, 0, A.length-1, temp);
		System.out.println("MergeSort:"+(System.nanoTime()-time));
		for (int i : A) {
			System.out.println(i);	
		}
	}

打印内容如下：

1
2
3
4
5
6
7
8
9
10
MergeSort:42863
1
1
2
4
5
8
9
25
477

csdn地址：http://blog.csdn.net/u012534831
github地址：https://github.com/qht1003077897
个人博客地址：https://qht1003077897.github.io
QQ：1003077897