归并排序

发表于 更新于 分类于 ， 本文字数： 1k 阅读时长 ≈ 2 分钟

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

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

先写排序的模板

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;
}