洛谷：P1177：排序（模版）

题目

P1177：排序（模版）

分析

题目说了，这是一个“模版”，用来帮助我们理解分治的基本思想和基本应用（归并排序）。

基本的分治思想

很简单，分治就是“分而治之”。以排序为例，如果数组里有很多数据，之前的初级排序都会很耗时（例如：冒泡排序就是典型的时间复杂度在\(O(N^2)\)的算法）。怎么加快呢？冒泡排序之所以慢，是因为一个数值到达最终位置的时候，要多次与相邻数值比较。直觉告诉我们：如果比较次数少了，速度自然就快了。降低比较次数，从降低要比较的数量开始。

将整个数据集分成左右两半：\([L, R] \Rightarrow [L, m], [m+1, R]\)，其中\(m=\frac{L+R}{2}\)。对于这两个小区间，又可以各自两分……直到区间只有一个数，就是自然排好序的。这种两分思路可以缩短总的比较次数，但还有一个问题没有解决：两个区间有序了，但如何整合到一个更大的区间使其有序？

归并思路

观察如下两个区间各自排序后的数据：

A: [1 4 | 2 5]

显然，最后排好序的数组应该是1 2 4 5。

这里可以用双指针法分别指示左右区间下一个要看的数字的位置（分别是i和j），同时用一个临时数组tmp[]来存放：

1. \(A[i]\le A[j]\)，说明A[i]在前，拿出A[i]给tmp[k]——这里的k指示tmp数组中下一个要处理的位置。A数组左边部分要看下一个（i++）。tmp数组的定位也要前进一次（k++）。
2. \(A[i]\gt A[j]\)，说明A[j]在前，拿出A[j]给tmp[k]——这里的k指示tmp数组中下一个要处理的位置。A数组右边部分要看下一个（i++）。tmp数组的定位也要前进一次（k++）。
3. 上述循环一直进行到i>mid||j>R为止：while(i<=mid && j<=R)
4. 上述循环结束后，要么左边区间、要么右边区间还有数据留存，所以要将这些数据转移到tmp中。

    while(i<=mid)
    {
        tmp[k++]=a[i++];
    }
    while(j<=r)
    {
        tmp[k++]=a[j++];
    }
    for(int i=0;i<k;i++)
    {
        a[l+i]=tmp[i];
    }

5. 将tmp数组拷贝回A数组，以便进行下一次合并。

这就是归并排序的核心思路。

答案

思考

请牢记这个模板。