（10）排序算法——归并排序

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

1、基本思想：

归并排序是分治法的一个非常典型的应用，它是将已有序的子序列进行合并，并使合并之后的序列仍然有序。将两个有序序列合并成一个序列，称为二路归并。

归并算法通常使用递归实现，按照n/2不断将数组拆分，直到子数组无法再拆分，然后递归的递归调用归并排序。

简单的说归并排序算法包括两步：

  1. 划分子表。
  2. 合并子表。

2、算法描述：

假设有数组arr[n]，升序排列。

  1. 将n个元素分成两个含n/2个元素的子序列。
  2. 分别将两个子序列递归排序，最终原序列会拆分成n个子序列，每个含有一个元素。此时每个子序列都被当做已排好序。
  3. 合并两个已排好序的序列。
  4. 合并操作首先申请空间，大小为要合并的两个数组的和，用来存放排序后的数组。
  5. 在两个数组中分别取出第一个元素，将较小的元素放入新数组中。然后继续取该数组的下一个元素比较，直到任意一个数组比较完成。
  6. 将剩余数组的剩余元素直接放到新数组中即可。


3、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
/**
 * 归并排序
 * @author lizhen
 */
public class MergeSort {
	/**
	 * 升序排序
	 * 主要分为两步：
	 * 1、拆分数组
	 * 2、归并数组
	 * @param arr 要排序的数组
	 * @param left 本次排序的数组的起点
	 * @param right 本次排序的数组的终点
	 */
	public void mergeSort(int[] arr, int left, int right) {
		if (left < right) {
			//1、拆分
			int center = (right + left)>>1;
			mergeSort(arr, left, center);
			mergeSort(arr, center + 1, right);
			//2、归并
			int[] data = merge(arr,left,center,right);
			//输出当前排序的临时数组
			ArrayUtil arrayUtil = new ArrayUtil();
			arrayUtil.printArray(data);
		}
	}
	public int[] merge(int[] arr, int left, int center, int right) {
		int[] data = new int[right - left + 1];
		int i = left;
		int j = center + 1;
		int k = right;
		int dateIndex = 0;
		// 不断比较两个数组首个元素
		while (i <= center && j <= right) {
			if (arr[i] <= arr[j])
				data[dateIndex++] = arr[i++];
			else
				data[dateIndex++] = arr[j++];
		}
		// 将两个子数组剩余的元素加入到data中
		while (i <= center)
			data[dateIndex++] = arr[i++];
		while (j <= right)
			data[dateIndex++] = arr[j++];
		//将排好序的数组合并到原数组中
		for(i=0,j=left;j<=right;j++,i++){
			arr[j] = data[i];
		}
		return data;
	}
}

4、效率分析：