2.2.12

上次更新:2020-08-02
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

中文版的翻译比较难理解。
实际上就是另一种归并排序的实现方式。
先把数组分成若干个大小为 M 的块 。
对于每个块,用选择排序进行排序 。
随后遍历数组,将各个块归并起来。
归并时仅复制右侧数组就够了,然后倒着归并(从右到左),可以将额外空间降到 M。

具体归并流程如下:

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

在这个流程中左侧数组的指针i是不会大于归并的写入指针k的。
最坏情况下,aux用尽时 i == k,左侧数组可以直接并上去。

代码

using System;
using Merge;

namespace _2._2._12
{
    /// <summary>
    /// 归并排序类。
    /// </summary>
    public class MergeSort : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MergeSort() { }

        /// <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);
            }
            // 将各个块合并。
            var aux = new T[M];
            for (var i = 0; i < blockNum - 1; i++)
            {
                Merge(a, aux, 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="aux">辅助数组。</param>
        /// <param name="lo">范围起点。</param>
        /// <param name="mid">范围中点。</param>
        /// <param name="hi">范围终点。</param>
        private void Merge<T>(T[] a, T[] aux, int lo, int mid, int hi) where T : IComparable<T>
        {
            for (var k = mid + 1; k <= hi; k++)
            {
                aux[k - mid - 1] = a[k];
            }

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

另请参阅

Merge 库

上一题 下一题