合并排序与分治法

合并排序

考虑两个有序的数组，我们如何将它合并成第三个有序的数组？

比如：

a=[1, 3, 5, 7]

b=[2,4,4 ]

分用左手和右手从a,b数组中拿出元素，如果左手的小，就放第三个有序数组中去，反之，就把右手的放到第三个数组中，然后用空着的手取下一个：

------------

1357

↓取a1

244

------------

357

1 2

↑取b2

244

---------

357

↓取a2

123

--------

1234

↑取b2

----------

12344

↑ 取b3

----------

5 7

↓ ↓取a3a4

123445 7

这样，就可以将两个有序数组合成一个有序数组。

让我考虑更多的情况：

A1:考虑 1个元素的数组，本身为已序。

A2:两个元素的数组，可以看为将两个分别含有1个元素的数组合并成第三个已序的数组。

A3:可以归结为A2+A1的过程，然后再合并一次。

A4:归结为A2+A2的过程，然后再合并一次。

。。。

对于An,我们可以将它看作两个分别是两个A(n/2)合并一次的过程。

这就是我们所说的合并排序。

合并排序是所说的分治法，分治法一般要3步：

1，分解，将问题n分解为两个 n/2 直到我们能直接解决的数。

2，解决问题。

3，合并，将分解以后的问题。

看图演示一个合并排序过程：

合并排序与分治法

代码就是明显的递归模式了。

importrandom
defmerge(a, left, right , end):
'''merge two sorted sequence
left right end of merge(Not include)
a[left:right]
a[right:end]
'''
llen=right - left
rlen=end - right
al=a[left:right]
al.append(None)
ar=a[right:end]
ar.append(None)
l=0
r=0
#print '<',left,right,end
#print 'lr', al,ar
#print a
fori inrange(end - left):
ifal[l] != None andar[r] != None and(al[l] <= ar[r]):
a[left+i] = al[l]
l=l+1
elifal[l] != None andar[r] != None :
a[left+i] = ar[r]
r=r+1
elif ar[r] == None andal[l] != None:#right array is empty
a[left+i:end] = al[l:right-left]
break
elifal[l] == None andar[r] != None:
a[left+i:end] = ar[r:end-right]
break
returna

defmerge_sort(a,s,e):
'''
array
[s:e+1]python slice [)
'''
ifs < e:
m=(s+e)/2
merge_sort(a, s, m ) #a[s:m+1]python slice [)
merge_sort(a, m+1 , e)#a[m+1:e][m+1:e+1] python slice [)
merge(a, s,m+1,e+1)
returna

forx inrange(10000):
a=[]
b=list()
n=random.randint(100,1130)
fori inrange(1000):
b.append(i)
fori inrange(n):
#choose 9random numbers in (1...1000) as a sort list
a.append( random.choice(b))
b= merge_sort(a,0,n-1)
ifb!= sorted(a):
print'err',n, x
printa
printb
printsorted(a)

#a=[0, 177, 911, 453, 566, 985]
#print merge_sort(a,0,5)
#print merge(a,0,3,6)
#print a

画图使用gravpviz的dot,源代码如下：

digraphmerge{
charset="utf-8";
node[shape=plaintext, fontsize=16];
"寮€濮?quot;->"鍒嗚В"->"鎺掑簭"->"鍚堝苟";

node[shape=box,rotate=90];

node[width=3];
{rank=same;"5 2 4 7 1 3 6 2";"寮€濮?quot;;}
node[width=1.5];
"5 2 4 7 1 3 6 2"->"5 2 4 7";
"5 2 4 7 1 3 6 2"->"1 3 6 2";
{rank=same;"5 2 4 7";"1 3 6 2";}

node[width=.75];
{rank=sname;"52";"47";"13";"62";}
"5 2 4 7"->"52";
"5 2 4 7"->"47";
"1 3 6 2"->"13";
"1 3 6 2"->"62";

{rank=same;"5";"2";"4";"7";"1";"3";"6";"2 ";"鍒嗚В";}

"52"->5;
"52"->2;
"47"->4;
"47"->7;
"13"->1;
"13"->3;
"62"->"6";
"62"->"2 ";
{rank=same;"2 5";"4 7";"1 3";"2 6";"鎺掑簭";}
5->"2 5";
2->"2 5";
4->"4 7";
7->"4 7";
1->"1 3";
3->"1 3";
"6"->"2 6";
"2 "->"2 6";
node[width=1.5];
{rank=same;"2 4 5 7";"1 2 3 6";}
"2 5"->"2 4 5 7";
"4 7"->"2 4 5 7";
"1 3"->"1 2 3 6";
"2 6"->"1 2 3 6";
node[width=3];
"2 4 5 7"->"1 2 2 3 4 5 6 7";
"1 2 3 6"->"1 2 2 3 4 5 6 7";
{rank=same;"1 2 2 3 4 5 6 7";"鍚堝苟";}
}

分治法使用递归，递归的讨论放到一篇里讨论。

合并排序与分治法

相关推荐