鱼喃

听！布鲁布鲁，大鱼又在那叨叨了

归并排序与分治法---化繁为简，分而治之

Posted on Views: 99+

归并排序（Merge sort）是一种建立在归并操作上的排序算法。该算法采用了分治法（Divide and Conquer）的思想。

算法原理

将一个较长的序列划分成几个短一点的子序列，然后子序列继续递归划分，直到子序列的规模足够小时，对子序列排序（治），将排好序的子序列合并为较长的子序列，最终实现将整个序列排序的目的。其基本思想就是将大规模的问题转换成独立的、同等的、容易解决的子问题，最后合并有序的子问题就解决了整个问题。

归并操作的过程如下

假定有两个已排好序的子序列A1、A2；

  1. 申请空间用来临时存放合并后的新序列A3，A3.size()>=A1.size()+A2.size()；
  2. 设定两个标记，最初位置分别为A1、A2的起始位置；
  3. 比较两个标记所指向的元素，选择相对小的元素追加到A3，并移动该标记到下一位置；
  4. 重复步骤3直到其中一个标记到达该子序列尾；
  5. 将另一子序列剩下的所有元素追加到A3；

算法演示

借用一张维基百科的图来形象的演示这一过程（点击查看原图）。

归并排序示意图

（一个归并排序的例子：对一个随机点的链表进行排序）

例如给这么一个数组排序：{41, 8467, 6334, 6500, 9169}

分

Step 1 –>  { {41, 8467}, {6334, 6500, 9169} }

Step 2 –> { { {41}, {8467} },{ {6334}, {6500, 9169} } }

Step 3 –> { { {41}, {8467} },{ {6334}, { {6500}, {9169} } } }

治、合

Step 4 –> { {41, 8467}, { {6334}, {6500, 9169} } }

Step 5 –> { {41, 8467}, {6334, 6500, 9169} }

Step 6 –> { 41, 6334, 6500, 8467, 9169 }

时间复杂度

我们都知道，将一个大数N每次除以2，最多需要logN次就跟1相差无几了，所以归并排序最多需要logN次划分就可以将一个有N个元素的数组大小降到1的规模，处理该子数组的时间复杂度是O(1)，而同等规模的子数组共有 N/size * size=N 。所以，一共需要logN * N

的时间复杂度，也就是O（NlogN）。

有意思的是，归并排序的最好、最差、平均时间复杂度都是 O(NlogN)。也就是说，它的处理时间完全不依靠输入元素的有序情况，只与问题的规模有关。RP低的同学一定会喜欢归并排序的^-^。

综上，归并排序的最好、最差、平均时间复杂度都是 O(NlogN)，效率较高，但是占用内存大。

算法稳定性

归并排序的合并过程处理的是相邻的子序列，只要注意在合并过程中遇到左右元素相同时，左边序列享有更高的优先级，就不会改变相等元素的相对位置，所以归并排序是一种稳定的排序算法。

示例代码（C++）

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
/*
普通的归并排序
int * src：所需排序的数据
index_s：所需排序的数据首地址
index_e：所需排序的数据第一个无效地址
*/

int merge_sort(int * src, int index_s, int index_e)
{
	/*治*/
	if(index_e - index_s <= 1)
	{
		return 0;
	}

	int index_l_s = index_s;
	int index_l_e = (index_e + index_s) / 2;
	int index_r_s = (index_e + index_s) / 2;
	int index_r_e = index_e;

	/*分*/
	merge_sort(src, index_l_s, index_l_e);
	merge_sort(src, index_r_s, index_r_e);

	//开辟额外的内存来保存中间结果
	int* tmp = new int[index_e - index_s];
	int cnt = 0;
	int i = index_l_s;
	int j = index_r_s;

	/*合
	 *合并左右两个数组
	 */
	for(; i<index_l_e && j<index_r_e; )
	{
		if(src[i]<=src[j])
		{
			tmp[cnt++] = src[i++];
		}else
		{
			tmp[cnt++] = src[j++];
		}
	}

	/*处理剩余*/
	for(; i<index_l_e; i++)
	{
		tmp[cnt++] = src[i];
	}

	for(; j<index_r_e; j++)
	{
		tmp[cnt++] = src[j];
	}

	/*把排好序的写回原数组的对应位置*/
	for(int i=index_l_s; i<index_r_e; i++){
		src[i]=tmp[i-index_s];
	}

	delete []tmp;
	return 0;
}

详细代码请点击这里查看。

算法改进

1、从示例代码可以看出，每次合并的时候都需要申请临时空间，其实可以只申请一次，重复利用（代码见附件）；

2、消去递归，用栈的形式来替代（代码见附件）；

3、取消临时空间的申请，也就是从底而上的归并排序。写过一次，但是感觉就是希尔排序，下次写希尔排序的时候再分析吧。

4、一般用的都是二路归并，可以采用多路归并来提高。（仅针对递归情况）

详细代码请点击这里查看。