2.2.17

2.2.17 #

解答 #

排序方式和 2.2.16 十分类似，不再赘述，这里介绍一下归并方法。

如 gif 图所示，先把要归并的两个链表拆出来，随后确定表头位置，然后进行归并即可。归并结束后返回 first。

结果分析如下图所示：

随着有序部分的增加，对于相同大小的数组自然归并排序的耗时会缩短。

对于有序部分相同的情况，随着数组大小的倍增，耗时呈现了O(nlogn)的趋势。

代码 #

public class MergeSortNatural : BaseSort
{
    /// <summary>
    /// 利用自然的归并排序进行自底向上的排序。
    /// </summary>
    /// <typeparam name="T">用于排序的元素类型。</typeparam>
    /// <param name="a">需要排序的数组。</param>
    public override void Sort<T>(T[] a)
    {
        var aux = new T[a.Length];

        while (true)
        {
            // 找到第一个块
            var lo = 0;
            var mid = FindBlock(lo, a) - 1;
            if (mid == a.Length - 1)
                break;

            while (mid < a.Length - 1)
            {
                var hi = FindBlock(mid + 1, a) + mid;
                Merge(lo, mid, hi, a, aux);
                lo = hi + 1;
                mid = FindBlock(lo, a) + lo - 1;
            }
        }
        Debug.Assert(IsSorted(a));
    }

    /// <summary>
    /// 将两个块归并。
    /// </summary>
    /// <typeparam name="T">数组的元素类型。</typeparam>
    /// <param name="lo">第一个块的开始下标。</param>
    /// <param name="mid">第一个块的结束下标（第二个块的开始下标 - 1）。</param>
    /// <param name="hi">第二个块的结束下标。</param>
    /// <param name="a">需要归并的数组。</param>
    /// <param name="aux">辅助数组。</param>
    private void Merge<T>(int lo, int mid, int hi, T[] a, T[] aux) where T : IComparable<T>
    {
        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++;
            }
        }
    }

    /// <summary>
    /// 获取下一个有序块。
    /// </summary>
    /// <typeparam name="T">数组元素类型。</typeparam>
    /// <param name="lo">查找起点。</param>
    /// <param name="a">用于查找的数组。</param>
    /// <returns>块的大小。</returns>
    private int FindBlock<T>(int lo, T[] a) where T : IComparable<T>
    {
        var size = 1;
        for (var i = lo; i < a.Length - 1; i++)
        {
            if (Less(a[i], a[i + 1]) || a[i].Equals(a[i + 1]))
                size++;
            else
                break;
        }
        return size;
    }
}

另请参阅 #

Merge 库