排序(6) 归并排序

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

归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度，代价是需要额外的内存空间。 归并排序算法将数组每一次都分解为原来的一半大小的两个子数组，当分解到了右边界比左边界还大的时候，不再分解，开始排序。 然后将排序好的子数组逐级合并，最后得到的结果就是排序好的数组。

归并排序

思想

归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

在这里我们只不过是利用了递归的思想，将数组每一次都分解为原来的一半大小的两个子数组，当分解到了右边界比左边界还大的时候，不再分解，开始排序。然后将排序好的子数组逐级合并，最后得到的结果就是排序好的数组。

首先考虑下如何将两个有序数列合并。这个非常简单，只要从比较两个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。这需要将待排序序列中的所有记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行 logn次，因此，总的时间复杂度为O(nlogn)。

归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果，因此空间复杂度为O(n)。

归并算法需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。

递归

所谓递归，指的是程序直接或间接调用本身的一种方法，它通常把一个大型的、复杂的问题不直接解决，而是转化成为一个与原问题相似的、规模较小的问题来解决。
简单来说， 递归就是把问题层层分解，直到程序出口处。
任何递归都必须有递归调用的结束条件，否则，程序将会陷入无限递归而无法结束，而这个结束条件满足时，一定不会调用本身，否则递归调用将无法结束。

算法描述

归并排序的算法伪代码：

归并排序的算法伪代码
1
2
3
4
5
6
7
8
public static void mergeSort(int[] arr) {
    if (arr.length > 1) {
        mergeSort(arr[0 ... arr.length/2]);
        mergeSort(arr[arr.length/2 + 1 ... arr.length]);
        merge arr[0 ... arr.length / 2] with 
            arr[arr.length/2 + 1 ... arr.length];
    }
}

对数列 {2, 9, 5, 4, 8, 1, 6, 7} 进行归并排序。
先进行 拆分数列，直到数列只有一个元素为止，然后，再将其 归并为一个新的有序数列。
递归调用持续将数组划分为子数组，直到每个子数组只包含一个元素。然后，该算法将这些小的子数组归并为稍大的有序子数组，直到最后形成一个有序的数组。

归并排序（法一）

归并排序利用的是分治的思想，对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的子序列，之后对子序列排序，后再用递归方法将排好序的子序列合并成为有序序列。

合并两个子序列时，需要申请两个子序列加起来长度的内存，临时存储新的生成序列，再将新生成的序列赋值到原数组相应的位置。
MergeSort方法在分解过程中创建两个临时数组，将数组前半部分和后半部分复制到临时数组中，对临时数组排序，然后将它们归并到原始数组中，这样产生很多额外的空间开销。

代码如下：

归并排序（）
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
public class MergeSort {	
	public static void mergeSort(int[] list) {
		if (list.length > 1) {
			// 对前半部分进行归并
			int[] firstHalf = new int[list.length / 2];
			System.arraycopy(list, 0, firstHalf,
			   0, list.length / 2);
			mergeSort(firstHalf);

			// 对后半部分进行归并
			int secondHalfLength = list.length - list.length / 2;
			int[] secondHalf = new int[secondHalfLength];
			System.arraycopy(list, list.length / 2, secondHalf, 
				0, secondHalfLength);
			mergeSort(secondHalf);

			// 把两部分数列合并到一个数列中
			merge(firstHalf, secondHalf, list);
		}
	}

	public static void merge(int[] list1, int[] list2, int[] temp) {
		int current1 = 0;
		int current2 = 0;
		int current3 = 0;

		while (current1 < list1.length && current2 < list2.length) {
			if (list1[current1] < list2[current2])
				temp[current3++] = list1[current1++];
			else
				temp[current3++] = list2[current2++];
		}

		while (current1 < list1.length)
			temp[current3++] = list1[current1++];

		while (current2 < list2.length)
			temp[current3++] = list2[current2++];
	}

	public static void main(String[] args) {
		int[] list = { 2, 3, 2, 5, 6, 1, -2, 3, 14, 12 };
		mergeSort(list);
		for (int i = 0; i < list.length; i++)
			System.out.print(list[i] + " ");
	}
}

在方法二中，递归地对数组的前半部分和后半部分进行排序，而不创建新的临时数组，然后把两个数组归并到一个临时数组中并将它的内容复制到初始数组中。

归并排序（推荐）

归并排序（法二）
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
public class MergeSort {
	public static void mergeSort(int[] arr, int left, int right) {
		if (left == right) {
			return;
		} else {
			//  取中间的数进行拆分
			int mid = (left + right) / 2;
			//  左边的数不断进行拆分
			mergeSort(arr, left, mid);
			//  右边的数不断进行拆分
			mergeSort(arr, mid + 1, right);

			// 合并
			merge(arr, left, mid + 1, right);
		}
	}

	public static void merge(int[] arr, int left, int mid, int right) {
		int[] leftArray = new int[mid - left];
		int[] rightArray = new int[right - mid + 1];
		for (int i = left; i < mid; i++) {
			leftArray[i - left] = arr[i];
		}
		for (int i = mid; i <= right; i++) {
			rightArray[i - mid] = arr[i];
		}

		int i = 0, j = 0;
		int k = left;

		while (i < leftArray.length && j < rightArray.length) {
			if (leftArray[i] < rightArray[j]) {
				arr[k++] = leftArray[i++];
			} else {
				arr[k++] = rigthArray[j++];
			}
		}

		while (i < leftArray.length) {
			arr[k++] = leftArray[i++];
		}
		while (j < rightArray.length) {
			arr[k++] = rigthArray[j++];
		}
	}

	public static void main(String[] args) {
		int[] arrays = { 9, 2, 5, 1, 3, 2, 1, 3, 2, 8, 7, 10 };
		//设置4个值的断点查看递归调用栈变化
		//int[] arrays = { 9, 2, 5, 1 };
		mergeSort(arrays, 0, arrays.length - 1);
		System.out.println(Arrays.toString(arrays));
	}
}

可以在Eclipse的debug中设置断点，查看递归调用和返回的次序，注意观察变量值的变化。

算法复杂度及稳定性

算法复杂度：
时间复杂度（平均）： O(nlogn)
时间复杂度（最坏）： O(nlogn)
时间复杂度（最好）： O(nlogn)

空间复杂度： O(n)

在这里我们只不过是利用了递归的思想，将数组每一次都分解为原来的一半大小的两个子数组，当分解到了右边界比左边界还大的时候，不再分解，开始排序。然后将排序好的子数组逐级合并，最后得到的结果就是排序好的数组。

原数组的长度为n，则细分得最大深度为logn，每一层需要排序的元素为n；则归并排序的时间复杂度为O(nlogn)。

稳定性：因为交换元素时，可以在相等的情况下做出不移动的限制，所以归并排序是可以稳定的。

0%