2.3.16

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

解答

官方实现见:https://algs4.cs.princeton.edu/23quicksort/QuickBest.java.html

类似于快速排序的结构,只要中点的两边都是最佳情况,那么整个数组就是最佳情况了。
具体方法是:
首先构造一个有序数组,
然后找到中点(作为枢轴),
对中点左右两侧子数组进行构造,
将选择的枢轴放到开始处(a[lo])。

代码

用于构造最佳数组的类。

namespace Quick
{
    /// <summary>
    /// 构建快速排序最佳情况的类。
    /// </summary>
    public class QuickBest
    {
        /// <summary>
        /// 构造函数,这个类不应该被实例化。
        /// </summary>
        private QuickBest() { }

        /// <summary>
        /// 构造适用于快速排序的最佳数组。
        /// </summary>
        /// <param name="n">数组长度。</param>
        /// <returns></returns>
        public static int[] Best(int n)
        {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = i;
            }
            Best(a, 0, n - 1);
            return a;
        }

        /// <summary>
        /// 递归的构造数组。
        /// </summary>
        /// <param name="a">需要构造的数组。</param>
        /// <param name="lo">构造的起始下标。</param>
        /// <param name="hi">构造的终止下标。</param>
        private static void Best(int[] a, int lo, int hi)
        {
            if (hi <= lo)
                return;
            int mid = lo + (hi - lo) / 2;
            Best(a, lo, mid - 1);
            Best(a, mid + 1, hi);
            Exch(a, lo, mid);
        }

        /// <summary>
        /// 交换数组中的两个元素。
        /// </summary>
        /// <typeparam name="T">数组的元素类型。</typeparam>
        /// <param name="a">包含要交换元素的数组。</param>
        /// <param name="x">需要交换的第一个元素下标。</param>
        /// <param name="y">需要交换的第二个元素下标。</param>
        private static void Exch(int[] a, int x, int y)
        {
            int t = a[x];
            a[x] = a[y];
            a[y] = t;
        }
    }
}

用于测试的方法

using System;
using Quick;

namespace _2._3._16
{
    /*
     * 2.3.16
     * 
     * 最佳情况。
     * 编写一段程序来生成使算法 2.5 中的 sort() 方法表现最佳的数组(无重复元素):
     * 数组大小为 N 且不包含重复元素,
     * 每次切分后两个子数组的大小最多差 1
     * (子数组的大小与含有 N 个相同元素的数组的切分情况相同)。
     * (对于这道练习,我们不需要在排序开始时打乱数组。)
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSortAnalyze quick = new QuickSortAnalyze
            {
                NeedShuffle = false,            // 关闭打乱
                NeedPath = true                 // 显示排序轨迹
            };
            int[] a = QuickBest.Best(10);
            for (int i = 0; i < 10; i++)
            {
                Console.Write(a[i] + " ");
            }
            Console.WriteLine();
            quick.Sort(a);
            for (int i = 0; i < 10; i++)
            {
                Console.Write(a[i] + " ");
            }
            Console.WriteLine();
        }
    }
}

另请参阅

Quick 库

上一题 下一题