2.2.12

2.2.12 #

解答 #

中文版的翻译比较难理解。

实际上就是另一种归并排序的实现方式。

先把数组分成若干个大小为 M 的块。

对于每个块，用选择排序进行排序。

随后遍历数组，将各个块归并起来。

归并时仅复制右侧数组就够了，然后倒着归并（从右到左），可以将额外空间降到 M。

具体归并流程如下：

复制右侧数组到 aux，现在右侧数组a[hi]~a[mid+1]中的元素可以被安全覆盖。
设定指针i,j,k，将数组 a[mid]~a[0] 和 aux[hi-mid-1]~aux[mid + 1] 归并到 a[hi - 1]~a[0]。

在这个流程中左侧数组的指针i是不会大于归并的写入指针k的。

最坏情况下，aux用尽时 i == k，左侧数组可以直接并上去。

代码 #

public class MergeSort : BaseSort
{
    /// <summary>
    /// 利用归并排序将数组按升序排序。
    /// </summary>
    /// <typeparam name="T">数组元素类型。</typeparam>
    /// <param name="a">待排序的数组。</param>
    public override void Sort<T>(T[] a)
    {
        Sort(a, 1);
    }

    /// <summary>
    /// 利用分块法进行归并排序。
    /// </summary>
    /// <typeparam name="T">待排序的数组内容。</typeparam>
    /// <param name="a">待排序的数组。</param>
    /// <param name="m">分块大小。</param>
    public void Sort<T>(T[] a, int m) where T : IComparable<T>
    {
        var blockNum = (a.Length + m - 1) / m;
        var selection = new SelectionSort();
        // 对块进行选择排序。
        for (var i = 0; i < blockNum; i++)
        {
            var lo = i * m;
            var hi = Math.Min((i + 1) * m - 1, a.Length - 1);
            selection.Sort(a, lo, hi);
        }
        // 将各个块合并。
        for (var i = 0; i < blockNum - 1; i++)
        {
            Merge(a, 0, (i + 1) * m - 1, Math.Min((i + 2) * m - 1, a.Length - 1));
        }
    }

    /// <summary>
    /// 将指定范围内的元素归并。
    /// </summary>
    /// <typeparam name="T">数组元素类型。</typeparam>
    /// <param name="a">原数组。</param>
    /// <param name="lo">范围起点。</param>
    /// <param name="mid">范围中点。</param>
    /// <param name="hi">范围终点。</param>
    private void Merge<T>(T[] a, int lo, int mid, int hi) where T : IComparable<T>
    {
        var aux = new T[hi - lo + 1];
        for (var k = lo; k <= hi; k++)
        {
            aux[k] = a[k];
        }

        int i = lo, j = mid + 1;
        for (var k = lo; k <= hi; k++)
        {
            if (i > mid)
            {
                a[k] = aux[j];
                j++;
            }
            else if (j > hi)
            {
                a[k] = aux[i];
                i++;
            }
            else if (Less(aux[j], aux[i]))
            {
                a[k] = aux[j];
                j++;
            }
            else
            {
                a[k] = aux[i];
                i++;
            }
        }
    }
}

另请参阅 #

Merge 库