归并排序

归并排序思路很简单, 但自己一直不会敲, 也没敲过。 大学算法课本上的代码丑得不行, 嫌弃得要死。 所以自己只知道它的思想。 这几天打高校遇到了求逆序数对的问题,用树状数组来写会爆内存,需要用到归并的思想。于是自己打算好好看一下归并排序,发现紫书上的代码非常简洁,心喜,很快就记住了这段代码,并用自己喜欢的风格敲了一遍。

自己对简洁的代码果真没有一丝抵抗力。

先写排序的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int A[MAXN], T[MAXN]; //A为原数组, T为辅助数组
void mergesort(int l, int r) //排序区间为[l, r)
{
if(r-l > 1)
{
int mid = l+r>>1;

mergesort(l, mid);
mergesort(mid, r);

int p=l, q=mid, i=l;

while(p < mid || q < r)
{
if( q>=r || ( p<mid && A[p] <= A[q] ) )
T[i++] = A[p++];
else
T[i++] = A[q++];
}

for(int i=l; i<r; i++)
A[i] = T[i];
}
}

代码的两个条件是关键。首先,只要有一个非空序列,就要继续合并 while( p < mid || q < r ),因此在比较时不能直接比较 A [p] 和 A [q], 因为可能其中一个序列为空, 从而 A [p] 或 A [q] 为一个实际不存在的元素。正确的方式是:

  • 如果第二个序列为空(此时第一个序列一定为非空),复制 A [p]。
  • 否则,当且仅当第一个序列也非空,且 A [p] <= A [q] 时,才复制 A [p]。

代码巧妙地利用短路运算符 || 把两个条件连接在了一起:如果条件 1 满足,就不是计算条件 2; 如果条件 1 不满足,就一定会计算条件 2。这样的技巧很实用。

排序传入的参数为起始与终止的数组下标,为左闭右开,传入的右端点应为实际的加 1。

下面为调用函数

1
2
3
4
5
6
7
8
9
10
int A[10] = {3, 6, 2, 1, 4, 5, 6, 7, 12, 10};
int T[10];

int main()
{
mergesort(0, 10); //右端点应使用r+1,即最后一个元素后面的位置
for(int i=0; i<10; i++)
printf("%-3d", A[i]);
return 0;
}