一、 归并排序原理
归并排序采用分治算法,将对整个数组排序的问题转化为合并两个有序子序列的问题。
一.1:思想方法
以上是对数组进行排序的过程。
首先,我们可认为,当区间长度为1时,每个区间都是有序的。
接着,我们合并这些长度为1的区间,得到了第二行数据,每个长度为2的区间都是有序的。
如果我们继续合并,就可以得到长度为4的有序区间。
我们最终只需要进行Log2(N)次合并即刻完成排序。
一.2:合并有序区间的方法
首先,我们需要一个临时空间TEMP,我们将上一轮排序完的两个区域放入临时数组,注意左半边顺序放,右边倒着放。
下来我们开始合并操作
二、 代码[ pascal]
<pre name="code" class="delphi">program msort;
const
maxn=100000000;
var
i,j,k,n:longint;
A,B,C:Array[0..maxn]of longint;
procedure init;
var
i:longint;
begin
randomize;
readln(n);
for i:=1 to n do A[i]:=random(1000000);
end;
procedure msort(l,r:longint);
var
i,j,k,mid:longint;
begin
if l=r then begin
B[l]:=A[l];
exit;
end;
mid:=(l+r)div 2;
msort(l,mid);
msort(mid+1,r);
for i:=l to mid do B[i]:=A[i];
k:=r;
for i:=mid+1 to r do begin
B[i]:=A[k];
dec(k);
end;
i:=l;j:=r;
for k:=l to r do begin
if B[i]<B[j]
then begin
A[k]:=B[i];
inc(i)
end
else begin
A[k]:=B[j];
dec(j);
end;
end;
end;
begin
init;
msort(1,n);
for i:=1 to n do writeln(A[i]);
end.
三、 归并排序求逆序对
TEMP |
25 |
37 |
48 |
57 |
82 |
75 |
29 |
18 |
这时刚才的一个临时数组,我们可以注意到,当右指针指的数字小于左指针的数字时候,他会比从左指针开始到中间的元素个数个逆序对。也就是MID-I+1个逆序对
为什么?因为左边是升序排列的。I右侧的元素只会比I大,所以假若TEMP[J]<I ,那TEMP[J]<TEMP[from i to mid]
因此只需要在源代码中加一行,即可完成任务
四、练习题。POJ罗楼