数据结构排序系列详解之七 归并排序

在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列，而归并排序的思想是：基于合并，将两个或两个以上有序表合并成一个新的有序表

归并排序算法：假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列长度为1,然后两两归并，得到n/2个长度为2（n为奇数的时候，最后一个序列的长度为1）的有序子序列。在此基础上，再对长度为2的有序子序列进行亮亮归并，得到若干个长度为4的有序子序列。如此重复，直到得到一个长度为n的有序序列为止。这种方法被称作是：2-路归并排序（基本操作是将待排序列中相邻的两个有序子序列合并成一个有序序列）。

算法实现代码如下：

package exp_sort;

public class MergeSort {

	/**
	 * 相邻两个有序子序列的合并算法
	 * 
	 * @param src_array
	 * @param low
	 * @param high
	 * @param des_array
	 */
	public static void Merge(int src_array[], int low, int high,
			int des_array[]) {
		int mid;
		int i, j, k;

		mid = (low + high) / 2;
		i = low;
		k = 0;
		j = mid + 1;

		// compare two list
		while (i <= mid && j <= high) {
			if (src_array[i] <= src_array[j]) {
				des_array[k] = src_array[i];
				i = i + 1;
			} else {
				des_array[k] = src_array[j];
				j = j + 1;
			}

			k = k + 1;
		}

		// if 1 have,cat
		while (i <= mid) {
			des_array[k] = src_array[i];
			k = k + 1;
			i = i + 1;

		}

		while (j <= high) {
			des_array[k] = src_array[j];
			k = k + 1;
			j = j + 1;
		}

		for (i = 0; i < k; i++) {
			src_array[low + i] = des_array[i];
		}

	}

	/**
	 * 2-路归并排序算法，递归实现
	 * 
	 * @param src_array
	 * @param low
	 * @param high
	 * @param des_array
	 */
	public static void mergeSort(int src_array[], int low, int high,
			int des_array[]) {
		int mid;
		if (low < high) {
			mid = (low + high) / 2;
			mergeSort(src_array, low, mid, des_array);
			mergeSort(src_array, mid + 1, high, des_array);
			Merge(src_array, low, high, des_array);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int array1[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
		int array2[] = new int[array1.length];
		mergeSort(array1, 0, array1.length - 1, array2);

		System.out.println("\n----------after sort-------------");
		for (int ii = 0; ii < array1.length; ii++) {
			System.out.print(array1[ii] + " ");
		}
		System.out.println("\n");
	}

}

代码解释：

归并排序中一趟归并要多次调用到2-路归并算法，一趟的归并的时间复杂度是O(n)，合并两个已经排好序的表的时间显然是线性的，因为最多进行了n-1次比较，其中n是元素的总数。如果有多个数，即n不为1时，递归的将前半部分数据和后半部分数据各自归并排序，得到排序后的两部分数据，再合并到一起。

算法分析：

该算法是建立在归并操作（也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作）上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，它将问题分成一些小的问题然后递归求解，而治的阶段则是将分的阶段解得的各个答案修补到一块；分治是递归非常有力的用法。注意：与快速·排序和堆排序比较，归并排序最大的特点就是，它一种稳定的排序方法。速度仅次于快速排序，一般用于对总体无序，但是各子项相对有序的数列。

复杂度：

时间复杂度为：O(nlogn) ——该算法最好、最坏和平均的时间性能。
空间复杂度为 ：O(n)
比较操作的次数介于(nlogn) / 2和 nlogn - n + 1之间。
赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n)
很难用于主存排序（归并排序比较占用内存，主要问题在于合并两个排序的表需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样的一些附加操作，其结果严重放慢了排序的速度）但是效率很高，主要用于外部排序，对于重要的内部排序应用而言，一般还是选择快速排序。

归并操作的步骤如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

归并排序的步骤如下（假设序列共有n个元素）：
将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素
将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
重复步骤2，直到所有元素排序完毕