2.3.19

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

解答

主要介绍一下这个少于七次比较的五取样算法。
首先假设五个数字为 a b c d e
对 b c 排序,d e 排序。(两次比较)
比较 b 和 d,把较小那一组换到 b c 的位置上去。(一次比较)
此时会有 b < c, b < d < e。
交换 a, b,重新对 b c 排序。(一次比较)
再次比较 b 和 d,把较小的那一组换到 b c 的位置上。(一次比较)
最后比较 c 和 d,较小的那一个即为中位数。(一次比较)
总共需要 6 次比较,严格小于 7 次。

取样完毕后,a b 是最小值和次小值(这里没有对应关系,a 也可以是次小值)。
d 和 e 是最大值和次大值(同样没有对应关系)。
我们把 d 和 e 放到数组的最后作为哨兵,去掉右边界的判断。
同时让左右两侧指针都向中间移动两位,减少不必要的比较。

测试结果,对比普通快排性能提升约 10%,和三取样快排区别不大。

代码

五取样快排

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._19
{
    /// <summary>
    /// 五取样快速排序
    /// </summary>
    public class QuickSortMedian5 : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortMedian5() {}

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(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>
        private void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;

            // 少于五个元素的数组直接进行插入排序
            if (hi - lo + 1 < 5)
            {
                int n = hi - lo + 1;
                for (int i = lo; i - lo < n; i++)
                {
                    for (int k = i; k > 0 && 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;

            // 假设为 a b c d e 五个数字
            // 首先对 b c 排序
            if (Less(a[lo + 2], a[lo + 1]))
                Exch(a, lo + 2, lo + 1);
            // 然后再排序 d e
            if (Less(a[lo + 4], a[lo + 3]))
                Exch(a, lo + 4, lo + 3);

            // 这时满足 b < c, d < e
            // 比较 b d,把较小的一组放到 b c 的位置上去
            if (Less(a[lo + 3], a[lo + 1]))
            {
                Exch(a, lo + 1, lo + 3);
                Exch(a, lo + 2, lo + 4);
            }

            // 这时满足 b < c, b < d < e,即 b 是 b c d e 中的最小值
            // 交换 a 和 b
            Exch(a, lo, lo + 1);

            // 重新排序 b c
            if (Less(a[lo + 2], a[lo + 1]))
                Exch(a, lo + 2, lo + 1);

            // 这时再次满足 b < c, d < e
            // 比较 b d,把最小的一组放到 b c 的位置上去
            if (Less(a[lo + 3], a[lo + 1]))
            {
                Exch(a, lo + 1, lo + 3);
                Exch(a, lo + 2, lo + 4);
            }

            // 这时 a 和 b 为五个数中的最小值和次小值(顺序不固定,a 也可以是次小值)
            // 最后比较 c 和 d,较小的那一个即为中位数(即第三小的数)
            if (Less(a[lo + 3], a[lo + 2]))
                Exch(a, lo + 3, lo + 2);

            // 此时 c 即为中位数
            Exch(a, lo, lo + 2);

            // d e 放到数组末尾充当哨兵
            Exch(a, lo + 3, hi);
            Exch(a, lo + 4, hi - 1);

            // 调整指针位置,前两位和后两位都已经在合适位置了
            j -= 2;
            i += 2;

            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v)) ;
                while (Less(v, a[--j])) ;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private 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;
            }
        }
    }
}

三取样快排

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._19
{
    /// <summary>
    /// 三取样快速排序
    /// </summary>
    public class QuickSortMedian3 : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortMedian3() {}

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(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>
        private void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;

            // 少于五个元素的数组直接进行插入排序
            if (hi - lo + 1 < 5)
            {
                int n = hi - lo + 1;
                for (int i = lo; i - lo < n; i++)
                {
                    for (int k = i; k > 0 && 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;

            if (Less(a[lo + 1], a[lo]))
                Exch(a, lo + 1, lo);
            if (Less(a[lo + 2], a[lo]))
                Exch(a, lo + 2, lo);
            if (Less(a[lo + 2], a[lo + 1]))
                Exch(a, lo + 1, lo + 2);

            Exch(a, lo, lo + 1);        // 中位数放最左侧
            Exch(a, hi, lo + 2);        // 较大的值放最右侧作为哨兵

            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v)) ;
                while (Less(v, a[--j])) ;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private 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;
            }
        }
    }
}

测试用例

using System;
using Quick;

namespace _2._3._19
{
    /*
     * 2.3.19
     * 
     * 五取样切分。
     * 实现一种基于随机抽取子数组中 5 个元素并取中位数进行切分的快速排序。
     * 将取样元素放在数组的一侧以保证只有中位数元素参与了切分。
     * 运行双倍测试来确定这项改动的效果,
     * 并和标准的快速排序以及三取样的快速排序(请见上一道练习)进行比较。
     * 附加题:找到一种对于任意输入都只需要少于 7 次比较的五取样算法。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quickNormal = new QuickSort();
            QuickSortMedian3 quickMedian3 = new QuickSortMedian3();
            QuickSortMedian5 quickMedian5 = new QuickSortMedian5();
            int arraySize = 200000;                         // 初始数组大小。
            const int trialTimes = 4;                       // 每次实验的重复次数。
            const int trialLevel = 6;                       // 双倍递增的次数。

            Console.WriteLine("n\tmedian5\tmedian3\tnormal\tmedian5/normal\t\tmedian5/median3");
            for (int i = 0; i < trialLevel; i++)
            {
                double timeMedian3 = 0;
                double timeMedian5 = 0;
                double timeNormal = 0;
                for (int j = 0; j < trialTimes; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(arraySize);
                    int[] b = new int[a.Length];
                    int[] c = new int[a.Length];
                    a.CopyTo(b, 0);
                    a.CopyTo(c, 0);
                    timeNormal += SortCompare.Time(quickNormal, a);
                    timeMedian3 += SortCompare.Time(quickMedian3, b);
                    timeMedian5 += SortCompare.Time(quickMedian5, c);
                }
                timeMedian5 /= trialTimes;
                timeMedian3 /= trialTimes;
                timeNormal /= trialTimes;
                Console.WriteLine(arraySize + "\t" + timeMedian5 + "\t" + timeMedian3 + "\t" + timeNormal + "\t" + timeMedian5 / timeNormal + "\t" + timeMedian5/timeMedian3);
                arraySize *= 2;
            }
        }
    }
}

另请参阅

Quick 库
Code to calculate “median of five” in C#

上一题 下一题