排序算法 – 归并排序

基本介绍

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之，时间复杂度为nlogn。

基本思想

1. 将序列中待排序数字分为若干组，最终每个数字分为一组。（默认长度为1的序列是有序的）
2. 将若干个组两两合并，保证合并后的组是有序的。（俩个子序列头部进行比较大小）
3. 重复第二步操作直到只剩下一组，排序完成。

归并排序思想示意图

分阶段可以理解为就是递归拆分子序列的过程。

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将 [4,5,7,8] 和 [1,2,3,6] 两个已经有序的子序列，合并为最终序列 [1,2,3,4,5,6,7,8] ，来看下实现步骤：

代码实现

template <class Type>
void mergepass(Type x[], Type y[], int s, int n) // 合并大小为 s的相邻子数组
{
    int i = 0;
    while (i <= n - 2 * s)
    {
        Merge(x，y，i，i + s - 1, i + 2 * s - 1); // 合并大小为s 的相邻 2段子数组
        i = i + 2 * s;
    }
    if (i + s < n) // 剩下的元素个数少于 2s
        Merge(x，y，i, i + s - 1，n - 1);
    else
        for (int j = i; j <= n - 1; j++)
            y[j] = x[j];
}
template <class Type>
void Merge(Type c[], Type d[], int l, int m, int r) // 合并c[l:m]和c[m+1:r]到 d[l:r]
{

    int i = l, j = m + 1, k = l;
    while ((i <= m) && (j <= r))
    {
        if (c[i] <= c[j])
            d[k++] = c[i++];
        else
            d[k++] = c[j++];
        if (i > m)
        {
            for (int q = j; q <= r; q++)
                d[k++] = c[q];
        }
        else
        {
            for (int q = i; q <= m; q++)
                d[k++] = c[q];
        }
    }
}