2.3.29

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

解答

在快排类内部添加一个随机数发生器,每次随机取枢轴并交换至第一位进行切分。

private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
{
    int i = lo, j = hi + 1;
    int pivot = this.RandomGenerator.Next(hi - lo) + lo;
    Exch(a, pivot, lo);
    T v = a[lo];
    while (true)
    {
        while (Less(a[++i], v))
            if (i == hi)
                break;
        while (Less(v, a[--j]))
            if (j == lo)
                break;
        if (i >= j)
            break;
        Exch(a, i, j);
    }
    Exch(a, lo, j);
    return j;
}

测试结果:

代码

使用随机枢轴的快排

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._29
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortRandomPivot : BaseSort
    {
        /// <summary>
        /// 切换到插入排序的阈值。
        /// </summary>
        public int M { get; set; }

        /// <summary>
        /// 随机数发生器。
        /// </summary>
        private readonly Random RandomGenerator = new Random();

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortRandomPivot()
        {
            this.M = 10;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        protected void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;
            if (hi - lo <= this.M)
            {
                // 调用插入排序
                for (int i = lo; i <= hi; i++)
                    for (int k = i; k > lo && Less(a[k], a[k - 1]); k--)
                        Exch(a, k, k - 1);
                return;
            }
            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            int pivot = this.RandomGenerator.Next(hi - lo) + lo;
            Exch(a, pivot, lo);
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }
    }
}

测试用例

using System;
using Quick;

namespace _2._3._29
{
    /*
     * 2.3.29
     * 
     * 随机化。
     * 用经验性的研究对比随机选择切分元素和正文所述的一开始就将数组随机化这两种策略的效果。
     * 在子数组大小为 M 时进行切换,将大小为 N 的不重复数组排序,
     * 其中 M=10、20 和 50,N=10^3、10^4、10^5 和 10^6。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("M\tN\tshuffle\trandom\tshuffle/random");
            Trial(10);
            Trial(20);
            Trial(50);
        }

        /// <summary>
        /// 进行一次测试。
        /// </summary>
        /// <param name="m">要使用的阈值</param>
        static void Trial(int m)
        {
            QuickSortInsertion withShuffle = new QuickSortInsertion();
            QuickSortRandomPivot randomPivot = new QuickSortRandomPivot();
            int trialTime = 5;

            // M=10
            withShuffle.M = m;
            randomPivot.M = m;
            double timeShuffle = 0;
            double timeRandomPivot = 0;
            for (int N = 1000; N < 10000000; N *= 10)
            {
                for (int i = 0; i < trialTime; i++)
                {
                    int[] a = new int[N];
                    int[] b = new int[N];
                    for (int j = 0; j < N; j++)
                    {
                        a[j] = j;
                    }
                    Shuffle(a);
                    a.CopyTo(b, 0);
                    timeShuffle += SortCompare.Time(withShuffle, a);
                    timeRandomPivot += SortCompare.Time(randomPivot, b);
                }
                timeShuffle /= trialTime;
                timeRandomPivot /= trialTime;
                Console.WriteLine(withShuffle.M + "\t" + N + "\t" + timeShuffle + "\t" + timeRandomPivot + "\t" + timeShuffle / timeRandomPivot);
            }
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        static void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

另请参阅

Quick 库

上一题 下一题