0%

排序-归并排序

发表于 更新于 分类于

概念

归并排序就是利用归并的思想实现的排序算法。归并排序的原理：假设初始序列含有n个记录，该序列可以看成n个有序的子序列，其中每个子序列的长度为1，然后两两归并，得到⌈n/2⌉（⌈x⌉表示不小于x的最小整数）个长度为2或者1的子序列，然后再两两归并，……，如此重复直到得到1个长度为n的有序序列为止。

递归式归并

演示
比如我们待排序的数组是 {9, 1, 5, 8, 3, 7, 4, 6, 2}，那么递归式的归并排序为流程为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
                 [9, 1, 5, 8, 3, 7, 4, 6, 2]
                    ↓                    ↓
          [9, 1, 5, 8, 3]             [7, 4, 6, 2]
           ↓            ↓              ↓         ↓ 
     [9, 1, 5]        [8, 3]      [7, 4]      [6, 2]
      ↓      ↓        ↓    ↓       ↓   ↓      ↓   ↓  
 [9, 1]     [5]      [8]  [3]     [7] [4]    [6]  [2]
  ↓  ↓       ↓        ↓    ↓       ↓   ↓      ↓   ↓  
[9]  [1]    [5]      [8]  [3]     [7] [4]    [6]  [2] // 上面为拆分，下面为归并(合并)
    ↓        ↓        ↓    ↓       ↓   ↓      ↓   ↓  
 [1, 9]     [5]      [8]  [3]     [7] [4]    [6]  [2]
      ↓      ↓        ↓    ↓        ↓  ↓      ↓   ↓
     [1, 5, 9]       [3, 8]        [4, 7]     [2, 6]
           ↓           ↓              ↓         ↓
         [1, 3, 5, 9, 8]              [2, 4, 6, 7]
                   ↓                    ↓
                 [1, 2, 3, 4, 5, 6, 7, 8, 9]

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 定义接口
interface Sorter {
	/**
	 * 将数组按升序排序
	 */
	int[] sort(int[] arr);

	/**
	 * 交换数组arr中的第i个位置和第j个位置的关键字
	 */
	default void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}

// 递归式归并排序
class MergeSorter implements Sorter {

	@Override
	public int[] sort(int[] arr) {
		int[] result = new int[arr.length];
		mergeSort(arr, result, 0, arr.length - 1);
		return result;
	}

	/**
	 * 将乱序的src[start...end]归并排序为有序的des[start...end]
	 * 
	 * @param src
	 *            归并前乱序数组
	 * @param des
	 *            归并后的有序数组
	 * @param start
	 *            归并的起始位置
	 * @param end
	 *            归并的终止位置
	 */
	private void mergeSort(int[] src, int[] des, int start, int end) {
		if (start == end) {
			des[start] = src[start];
			return;
		}
		int[] tmp = new int[src.length];
		// 将src[start...end]分为src[start...mid]和src[mid+1...end]两部分
		int mid = (start + end) / 2;
		mergeSort(src, tmp, start, mid); // 递归，将src[start...mid]归并为有序的tmp[start...mid]
		mergeSort(src, tmp, mid + 1, end); // 递归，将src[mid+1...end]归并为有序的tmp[mid+1...end]
		// 将有序的tmp[start...mid]和tmp[mid+1...end]合并为des[start...end]
		merge(tmp, des, start, mid, end);
	}

	/**
	 * 将有序的src[start, mid]和有序的src[mid+1, end]合并为有序的des[start,end];
	 * src可能为乱序数组,但是src[start, mid]和src[mid+1, end]是有序的。
	 * 
	 * @param src
	 *            乱序的原数组
	 * @param des
	 *            有序的目标数组
	 * @param start
	 *            数组第一部分起始位置
	 * @param mid
	 *            数组第一部分结束位置（两部分的分界点）
	 * @param end
	 *            数组第二部分结束位置
	 */
	protected void merge(int[] src, int[] des, int start, int mid, int end) {
		int i; // src数组第一部分下标
		int j; // src数组第二部分下标
		int k; // des数组下标
		// 将较小的数依次移动到目标数组中
		for (i = start, k = start, j = mid + 1; i <= mid && j <= end;) {
			if (src[i] < src[j]) {
				des[k] = src[i++];
			} else {
				des[k] = src[j++];
			}
			k++;
		}
		// 将剩余的src[i...mid]复制到des数组中
		for (; i <= mid; i++) {
			des[k] = src[i];
			k++;
		}

		// 将剩余的src[j...end]复制到des数组中
		for (; j <= end; j++) {
			des[k] = src[j];
			k++;
		}
	}
}

复杂度
时间复杂度：
因为归并的递归操作其实就是二叉树的结构，故而，最好情况 = 最坏情况 = 平均情况 = O(nlogn)

空间复杂度：
因为递归式归并需要(1)与原始记录相同大小的空间来存放归并的结果以及(2)深度为logn的栈空间，所以空间复杂度为O(n+logn)

非递归式归并

演示
又比如我们待排序的数组是 {9, 1, 5, 8, 3, 7, 4, 6, 2}，那么非递归式的归并排序为流程为：

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

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 非递归式归并排序
class NonRecursiveMergeSorter extends MergeSorter {

	@Override
	public int[] sort(int[] arr) {
		mergeSort(arr);
		return arr;
	}

	private void mergeSort(int[] arr) {
		int len = arr.length;
		int result[] = new int[len];
		int k = 1;
		while (k < len) {
			mergePass(arr, result, k); // arr归并至result,此时间隔为k
			k = 2 * k; // 子序列长度加倍
			mergePass(result, arr, k); // result归并至arr,此时间隔翻倍
			k = 2 * k; // 子序列长度加倍
		}
	}

	/**
	 * 将数组src中相邻长度为interval的子序列两两归并到des数组中
	 * 
	 * @param src
	 *            源数组
	 * @param des
	 *            目标数组
	 * @param interval
	 *            两两合并的子序列长度
	 */
	private void mergePass(int[] src, int[] des, int interval) {
		int i = 0;
		int len = src.length;
		while (i + 2 * interval - 1 < len) {
			// 两两合并
			merge(src, des, i, i + interval - 1, i + 2 * interval - 1);
			i = i + 2 * interval;
		}
		if (i + interval - 1 < len - 1) {
			// i+interval-1小于len-1，说明最后还剩余两个子序列，只不过最后的一个子序列长度不够interval
			// 那么将剩下的两个子序列进行合并
			merge(src, des, i, i + interval - 1, len - 1);
		} else {
			// 否则，最后只剩下单个子序列，则直接将该子序列加入到des尾部
			for (; i < len; i++) {
				des[i] = src[i];
			}
		}
	}
}

复杂度
时间复杂度：
同递归式归并，最好情况 = 最坏情况 = 平均情况 = O(nlogn)

空间复杂度：
非递归式归并不需要保存方法栈信息，所以空间复杂度为O(n)

所以非递归的递归算法性能要高于递归式归并算法。