排序算法---归并排序

归并排序中的“归并”的意思是将两个或者两个以上的有序表组合成一个新的有序表。他的实现无论是顺序存储结构还是链表结构，都可以在O(m+n)的时间级上实现。

 

复杂度：

时间复杂度：O(nlogn)

空间复杂度：O(n)

 

用途：

1、排序（速度仅次于快速排序，但较稳定）

2、求逆序对数

 

在实现单数组的归并排序之前，首先了解一下双数组的归并排序

这个双数组归并的前提是两个数组a和b都是已经排序好的

 

package sort;

import java.util.Arrays;

public class Test1 {
	public static void main(String args[])
	{
		int a[]={1,2,3,4,6,7,8,10};
		int b[]={1,2,5,9};
		int c[] = new int[a.length+b.length];
		mergeSort(a,a.length,b,b.length,c);
		System.out.println(Arrays.toString(c));
	}
	public static void mergeSort(int a[],int n,int b[],int m,int c[])
	{
		int i,j,k;
		i=j=k=0;
		//只有满足i<n&&j<m才执行，分别扫描两个数组，将数组中的元素进行对比，从小到大赋值给临时数组c
		while(i<n&&j<m)
		{
			if(a[i]<b[j])
				c[k++]=a[i++];
			else
				c[k++]=b[j++];
		}
		//将剩余的a数组的元素放入c中
		while(i<n)
		{
			c[k++]=a[i++];
		}
		//将剩余的b数组的元素放入c中
		while(j<m)
		{
			c[k++]=b[j++];
		}
	}
}

 

运行结果如下：

[1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

下面开始实现单数组的归并排序算法

例如：49  38  65  97  76  13  27

思想：首先将数组中个单独的一个元素作为一个已经排序好的序列，然后，将两两相邻的元素进行归并排序，依次类推，直到最后归并为一个排序好的序列

 

 如上图：

首先将每个元素作为一个已经排序好的序列，一共7个序列

然后，将每两个相邻的序列归并为一个序列，如49 38归并排序后变成 38 49，依次分成了4个序列，然后再将之前已经排序好的两个相邻的序列进行排序，变成2个序列，每个序列都是排序好的，最后归并为一个排序好的序列

 

实现代码：

 

package sort;

import java.util.Arrays;

public class MergeSort {
	public static void main(String args[])
	{
		int[] array = {49,38,65,97,76,13,27};
		System.out.println(Arrays.toString(array));
		System.out.println("---------排序前-------------");
		mergeSort(array,0,array.length-1);
		System.out.println("---------排序后-------------");
		System.out.println(Arrays.toString(array));
	}
	/**
	 * 这里依然需要递归来达到数组元素的排序，如果有两个已有元素的数组的话，就不用这么麻烦您了
	 * 不过这种归并排序依然是效率最好的排序方法之一，而且还是稳定的（相比快速排序，快速排序不稳定）
	 */
	public static void mergeSort(int array[],int low,int high)
	{
		if(low<high)
		{	
			mergeSort(array,low,(low+high)/2);//左边排序
			mergeSort(array,(low+high)/2+1,high);//右边排序
			merge(array,low,(high+low)/2,high);//将两个序列归并为一个序列
			System.out.println(Arrays.toString(array));	
		}
	}
	
	public static void merge(int array[],int low,int mid,int high)
	{
		int temp[]=new int[high-low+1];
		int i = low;
		int j = mid+1;
		int k=0;
		/**
		 * 将array数组分成两个数组来扫描，每一次都会将前后相邻的两个有序的序列归并为一个有序的序列
		 */
		while(i<=mid&&j<=high)
		{
			if(array[i]<=array[j])
				temp[k++]=array[i++];
			else
				temp[k++]=array[j++];	
		}
		//下面这两种while循环每次只执行其中一个
		//将剩余的array[i]存入temp中
		while(i<=mid)
		{
			temp[k++]=array[i++];
		}
		//将剩余的array[j]存放到temp中
		while(j<=high)
		{
			temp[k++]=array[j++];
		}
		for(int m=0;m<temp.length;m++)
		{
			array[low+m]=temp[m];
		}
		
	}
}

 

运行结果如下：

 

[49, 38, 65, 97, 76, 13, 27]

---------排序前-------------

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 97, 13, 76, 27]

[38, 49, 65, 97, 13, 27, 76]

[13, 27, 38, 49, 65, 76, 97]

---------排序后-------------

[13, 27, 38, 49, 65, 76, 97]