逍遥游

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

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

算法原理

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

归并操作的过程如下

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

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

算法演示

借用一张维基百科的图来形象的演示这一过程。

merge\_sort\_animation

(一个归并排序的例子:对一个随机点的链表进行排序)

例如给这么一个数组排序:{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
64
65
66
/*普通的归并排序
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、一般用的都是二路归并,可以采用多路归并来提高。(仅针对递归情况)

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


多说停止服务,disqus引导注册太过分,暂时不上评论系统了。有机会自己造轮子吧。邮箱:input@newnius.com