同样在 Github 上能够找到

写在前边

一体项目都托管在了 Github
上:
探索更为方便的版本见:
这一节内容只怕会用到的库文件有 Quick,同样在 Github 上可以找到。
善用 Ctrl + F 查找难题。

习题&题解

2.3.1

题目

遵守 Partition() 方法的轨道的格式给出该办法是什么样切分数组 E A S Y Q U E
S T I O N 的。

解答

图片 1

2.3.2

题目

信守本节中急速排序所示轨迹的格式给出急迅排序是何许将数组 E A S Y Q U E S
T I O N 排序的(出于演练的指标,能够忽视发轫打乱数组的片段)。

解答

图片 2

2.3.3

题目

对于长度为 N 的数组,在 Quick.sort()
试行时,其最大体素最多会被换来多少次?

解答

N / 2
在全速排序中,二个因素要被换来,有以下两种情形
1.该因素是枢轴,在切分的末梢一步被换到
2.该因素位于枢轴错误的两旁,需求被换到到另一侧去
只顾,以上三种景况在叁回切分中只会现出二遍

先是来看率先种情景,假设四个因素变为了枢轴
那正是说在后头的切分中该因素会被免除,空中楼阁继续的调换。
进而大家的指标应该是:
最大的要素总是出将来错误的两旁,同期切分的次数尽可能多。

接下去大家来构思什么协会那样的数组
鉴于大家本着的是最大的因素,因而「错误的边际」便是枢轴的左边手。
为了使切分的次数尽大概多,大家必要保持最大值移动的偏离尽量短。
但假若每一趟只移动壹个人的话,下三遍切分时最大值就能成为枢轴
比方 4 10 3 5 6,枢轴为 4,调换后数组变为:
4 3 10 5 6
随后 4 和 3 交换
3 4 10 5 6
下二次切分时 10 会产生枢轴,不再参预后续的切分。
故此大家须求让最大值每一次运动三个成分。

虚构上边包车型客车数组:
2 10 4 1 6 3 8 5 7 9
先是次切分的时候,枢轴为 2,10 和 1 实行互换
数组变为:
2 1 4 10 6 3 8 5 7 9
进而枢轴交流,数组变为:
1 2 4 10 6 3 8 5 7 9
第二次切分,枢轴为 4,10 和 3 进行置换。
1 2 4 3 6 10 8 5 7 9
跟着枢轴沟通 数组变为:
1 2 3 4 6 10 8 5 7 9
其三回切分,枢轴为 6,10 和 5 调换
1 2 3 4 6 5 8 10 7 9
随着枢轴交流,数组变为:
1 2 3 4 5 6 8 10 7 9
第陆次切分,枢轴为 8,10 和 7 调换
1 2 3 4 5 6 8 7 10 9
枢轴沟通,数组变为
1 2 3 4 5 6 7 8 10 9
末尾三次切分,枢轴为 10,直接交流
1 2 3 4 5 6 7 8 9 10

我们能够计算出要结构那样的数组的模板
a2 max a3 a1
其中 a1 < a2 < a3 < max
max 每轮切分移动两格,总共切分 N/ 2 次。

另请参阅

Number of largest element exchanges for quicksort-Stack
Overflow

2.3.4

题目

万一跳过以前打乱数组的操作,
提交五个带有 10 个要素的数组,
使得 Quick.sort() 所需的相比较次数高达最坏情况。

解答

历次只让枢轴变为已排序,那便是最坏意况。
这种时候枢轴是眼前子数组的最大值 / 最小值。
由于在大家的完成中接二连三取子数组的首先个因素作为枢轴。
于是多个已排序的数组能够达到规定的标准最坏情形,相比次数高达 O(n^ 2)。
假若换作取最后三个成分,最坏景况会化为逆序数组。

我们的完成中只要遇到与枢轴相等的因素也会终止循环,
之所以假设数组中有重复的因素会压缩比较次数。

例如:

1 2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10 11 12
4 5 6 7 8 9 10 11 12 13
5 6 7 8 9 10 11 12 13 14
6 7 8 9 10 11 12 13 14 15
另请参阅

Analysis of
Quicksort-khanacademy
Worst case for QuickSort – When can it occur?-Stack
Overflow

2.3.5

题目

付给一段代码将已知唯有二种主键值的数组排序。

解答

法定完结:

算法 gif 动图
图片 3

代码
namespace Quick
{
    /// <summary>
    /// 用于将只有两种元素的数组排序。
    /// </summary>
    public class Sort2Distinct : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public Sort2Distinct() { }

        /// <summary>
        /// 对数组 a 进行排序。
        /// </summary>
        /// <typeparam name="T">数组 a 的元素类型。</typeparam>
        /// <param name="a"></param>
        public override void Sort<T>(T[] a)
        {
            int lt = 0, gt = a.Length - 1;
            int i = 0;
            while (i <= gt)
            {
                int cmp = a[i].CompareTo(a[lt]);
                if (cmp < 0)
                    Exch(a, lt++, i++);
                else if (cmp > 0)
                    Exch(a, i, gt--);
                else
                    i++;
            }
        }
    }
}
另请参阅

Quick

2.3.6

题目

编排一段代码来测算 $ C_N $ 的正确值,
在 $ N=100、1000 $ 和 $10 000 $ 的动静下比较准确值和揣摸值 $ 2NlnN $
的出入。

解答

运转结果如下:
图片 4

代码

新建多少个 QuickSortAnalyze 类,在 QuickSort 的功底上加多一个 CompareCount
属性,用于记录相比次数。重写 Less 方法,每调用叁次就让 CompareCount 增添1 。

using System;
using System.Diagnostics;

namespace Quick
{
    /// <summary>
    /// 自动记录比较次数以及子数组数量的快速排序类。
    /// </summary>
    public class QuickSortAnalyze : BaseSort
    {
        /// <summary>
        /// 比较次数。
        /// </summary>
        public int CompareCount { get; set; }

        /// <summary>
        /// 是否启用打乱。
        /// </summary>
        public bool NeedShuffle { get; set; }

        /// <summary>
        /// 是否显示轨迹。
        /// </summary>
        public bool NeedPath { get; set; }

        /// <summary>
        /// 大小为 0 的子数组数量。
        /// </summary>
        public int Array0Num { get; set; }

        /// <summary>
        /// 大小为 1 的子数组数量。
        /// </summary>
        public int Array1Num { get; set; }

        /// <summary>
        /// 大小为 2 的子数组数量。
        /// </summary>
        public int Array2Num { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortAnalyze()
        {
            this.CompareCount = 0;
            this.NeedShuffle = true;
            this.NeedPath = false;
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
            this.CompareCount = 0;
            if (this.NeedShuffle)
                Shuffle(a);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write("  ");
                }
                Console.WriteLine("tlotjthi");
            }
            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 == 1)
                this.Array2Num++;
            else if (hi == lo)
                this.Array1Num++;
            else if (hi < lo)
                this.Array0Num++;

            if (hi <= lo)                   // 别越界
                return;
            int j = Partition(a, lo, hi);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write(a[i] + " ");
                }
                Console.WriteLine("t" + lo + "t" + j + "t" + 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;
            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;
        }

        /// <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;
            }
        }

        /// <summary>
        /// 比较第一个元素是否小于第二个元素。
        /// </summary>
        /// <typeparam name="T">要比较的元素类型。</typeparam>
        /// <param name="a">第一个元素。</param>
        /// <param name="b">第二个元素。</param>
        /// <returns></returns>
        new protected bool Less<T>(T a, T b) where T : IComparable<T>
        {
            this.CompareCount++;
            return a.CompareTo(b) < 0;
        }
    }
}

主方法

using System;
using Quick;

namespace _2._3._6
{
    /*
     * 2.3.6
     * 
     * 编写一段代码来计算 C_N 的准确值,
     * 在 N=100、1000 和 10 000 的情况下比较准确值和估计值 2NlnN 的差距。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Nt准确值t估计值t比值");
            QuickSortAnalyze sort = new QuickSortAnalyze();
            int N = 100;
            int trialTime = 500;
            for (int i = 0; i < 3; i++)
            {
                int sumOfCompare = 0;
                int[] a = new int[N];
                for (int j = 0; j < trialTime; j++)
                {
                    for (int k = 0; k < N; k++)
                    {
                        a[k] = k;
                    }
                    SortCompare.Shuffle(a);
                    sort.Sort(a);
                    sumOfCompare += sort.CompareCount;
                }
                int averageCompare = sumOfCompare / trialTime;
                double estimatedCompare = 2 * N * Math.Log(N);
                Console.WriteLine(N + "t" + averageCompare + "t" + (int)estimatedCompare + "t" + averageCompare / estimatedCompare);
                N *= 10;
            }
        }
    }
}
另请参阅

Quick

2.3.7

题目

在动用便捷排序将 N 个不另行的要素排序时,
估测计算大小为 0、1 和 2 的子数组的数目。假如您欣赏数学,请推导;
一经你不欣赏,请做一些实践并提议狐疑。

解答

本人讨厌数学= =

证明:
我们设 $ C_0(n) $ 代表将 $ n $ 个不重复成分排序时大小为 0
的数组的多少。
同理有 $ C_1(n) $ 和 $ C_2(n) $ 代表大小为 1 的数组的数目以致大小为 2
的数组的数码。
设 k 代表切分地点,明显切分地点随机且可能率相等,在 1~n 之间均匀布满。
依靠准绳,$ C_0(n), C_1(n),C_2(n) $ 都满意下式:
[ C(n)=
frac{sum_{k=1}^{n}(C(k-1)+C(n-k))}{n} ]
依赖飞快排序算法, $ sum_{k=1}^{n}C(k-1)=sum_{k=1}^{n}C(n-k) $
,因此
[
C(n)=frac{2sum_{k=1}^{n}C(k-1)}{n}\
nC(n)=2sum_{k-1}^{n}C(k-1) ]
同理代入 $ n-1 $ 有
[ (n-1)C(n-1)=2sum_{k-1}^{n-1}C(k-1)
]
相减
[ nC(n)-(n-1)C(n-1)=2C(n-1)\
C(n)=frac{n+1}{n}C(n-1) ]
利用累乘法求到通项公式
[ frac{C(n)}{C(n-1)}=frac{n+1}{n} \
frac{C(n)}{C(n-1)}timesfrac{C(n-1)}{C(n-2)}timesdotstimesfrac{C(m+1)}{C(m)}=
frac{n+1}{n}timesfrac{n}{n-1}timesdotstimesfrac{m+2}{m+1}\
frac{C(n)}{C(m)}=frac{n+1}{m+1}\
C(n)=C(m)frac{n+1}{m+1},n>m ]
对于 $ C_0(n) $ ,我们有始发规范 $ C_0(0)=1,
C_0(1)=0,C_0(2)=C_0(0)+C_0(1)=1 $
[ C_0(n)=frac{n+1}{3}, n>2
]
对于 $ C_1(n) $ ,大家有始发规范 $
C_1(0)=0,C_1(1)=1,C_1(2)=C_1(0)+C_1(1)=1 $
[ C_1(n)=frac{n+1}{3},n>2
]
对于 $ C_2(n) $ ,大家有始发规范 $
C_2(0)=C_2(1)=0,C_2(2)=1,C_2(3)=frac{2times(C_2(0)+C_2(1)+C_2(2))}{3}=frac{2}{3}
$
[ C_2(n)=frac{n+1}{6},n>3
]
结论
[ C_0(n)=C_1(n)=frac{n+1}{3},n>2
\ C_2(n)=frac{n+1}{6},n>3 ]
推行结果:
图片 5

代码

QuickSortAnalyze 类,增加了四个本性用于总括数组数量。

using System;
using System.Diagnostics;

namespace Quick
{
    /// <summary>
    /// 自动记录比较次数以及子数组数量的快速排序类。
    /// </summary>
    public class QuickSortAnalyze : BaseSort
    {
        /// <summary>
        /// 比较次数。
        /// </summary>
        public int CompareCount { get; set; }

        /// <summary>
        /// 是否启用打乱。
        /// </summary>
        public bool NeedShuffle { get; set; }

        /// <summary>
        /// 是否显示轨迹。
        /// </summary>
        public bool NeedPath { get; set; }

        /// <summary>
        /// 大小为 0 的子数组数量。
        /// </summary>
        public int Array0Num { get; set; }

        /// <summary>
        /// 大小为 1 的子数组数量。
        /// </summary>
        public int Array1Num { get; set; }

        /// <summary>
        /// 大小为 2 的子数组数量。
        /// </summary>
        public int Array2Num { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortAnalyze()
        {
            this.CompareCount = 0;
            this.NeedShuffle = true;
            this.NeedPath = false;
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
            this.CompareCount = 0;
            if (this.NeedShuffle)
                Shuffle(a);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write("  ");
                }
                Console.WriteLine("tlotjthi");
            }
            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 == 1)
                this.Array2Num++;
            else if (hi == lo)
                this.Array1Num++;
            else if (hi < lo)
                this.Array0Num++;

            if (hi <= lo)                   // 别越界
                return;
            int j = Partition(a, lo, hi);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write(a[i] + " ");
                }
                Console.WriteLine("t" + lo + "t" + j + "t" + 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;
            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;
        }

        /// <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;
            }
        }

        /// <summary>
        /// 比较第一个元素是否小于第二个元素。
        /// </summary>
        /// <typeparam name="T">要比较的元素类型。</typeparam>
        /// <param name="a">第一个元素。</param>
        /// <param name="b">第二个元素。</param>
        /// <returns></returns>
        new protected bool Less<T>(T a, T b) where T : IComparable<T>
        {
            this.CompareCount++;
            return a.CompareTo(b) < 0;
        }
    }
}

主方法

using System;
using Quick;

namespace _2._3._7
{
    /*
     * 2.3.7
     * 
     * 在使用快速排序将 N 个不重复的元素排序时,
     * 计算大小为 0、1 和 2 的子数组的数量。
     * 如果你喜欢数学,请推导;
     * 如果你不喜欢,请做一些实验并提出猜想。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            // 证明
            // 我们设 C0(n) 代表将 n 个不重复元素排序时大小为 0 的数组的数量。
            // 同理有 C1(n) 和 C2(n) 代表大小为 1 的数组的数量和大小为 2 的数组的数量。
            // 设 k 代表切分位置,显然切分位置随机且概率相等,在 1~n 之间均匀分布。
            // 根据条件,三者都满足下式。
            // C(n) = 1/n sum(C(k - 1) + C(n - k)), k=1,2,...,n
            // 显然 sum(C(k - 1)) = sum(C(n - k)), k=1,2,...,n
            // 于是可以化简为
            // C(n) = 2/n sum(C(k - 1)), k=1,2,...,n
            // nC(n) = 2 * sum(C(k-1)), k=1,2,...,n
            // 同理有
            // (n-1)C(n-1) = 2 * sum(C(k-1)), k = 1,2,...,n-1
            // 相减得到递推式
            // nC(n) - (n-1)C(n-1) = 2*C(n-1)
            // C(n) = (n+1)/n * C(n-1)
            // 利用累乘法可以求得通项公式
            // C(n)=C(k)*(n+1)/(k+1), n>k
            // 对于 C0 有 C0(0)=1, C0(1)=0
            // C0(2)=C(0)+C(1)=1
            // C0(n)=(n+1)/3, n>2
            // 对于 C1 有 C1(0)=0, C1(1)=1
            // C1(2)=C1(0)+C1(1)=1
            // C1(n)=(n+1)/3, n>2
            // 对于 C2 有 C2(0)=C2(1)=0, C2(2)=1
            // C2(3)=1/3*2*(C2(0)+C2(1)+C2(2))=2/3
            // C2(n)=C2(3)*(n+1)/4=(n+1)/6, n>3
            // 结论
            // C0(n)=C1(n)=(n+1)/3, C2(n)=(n+1)/6
            int n = 1000;
            QuickSortAnalyze sort = new QuickSortAnalyze();
            Console.WriteLine("nt0t1t2");
            for (int i = 0; i < 5; i++)
            {
                int[] a = new int[n];
                for (int j = 0; j < n; j++)
                {
                    a[j] = j;
                }
                SortCompare.Shuffle(a);
                sort.Sort(a);
                Console.WriteLine(n + "t" + sort.Array0Num + "t" + sort.Array1Num + "t" + sort.Array2Num);
                n *= 2;
            }
        }
    }
}
另请参阅

Quick

What is the expected number of subarrays of size 0, 1 and 2 when
quicksort is used to sort an array of N items with distinct keys?-Stack
Overflow

2.3.8

题目

Quick.sort() 在管理 N 个总体再度的因素时大约要求有个别次比较?

解答

历次切分都会把数组平分,共切分 logN 次(二分法),每一次切分比较 N 次(i
和 j 会壹人壹人地从两偏向中档靠拢)。
共比较 NlogN 次。

2.3.9

题目

请证实 Quick.sort()
在拍卖唯有三种主键值时的一言一动,以至在管理独有三种主键值的数组时的行为。

解答

切分时,枢轴右边都以自愧比不上(或等于)枢轴的,
右臂都是过量(或等于)枢轴的
独有二种主键值时,
第一回切分之后,某旁边的成分将全体同一
(假若枢轴选了相当的大的,那么左侧将全体等同,反之则侧边全体等同)

只有三种主键值时,和常常快速排序并无两样。
但假诺第一遍切分时精选了中间值作为枢轴,且中间值唯有四个
那便是说只供给一遍切分数组便会稳步。

2.3.10

题目

Chebyshev 不等式注明,一个随机变量的正式差别离均值大于 k 的可能率小于
1/k^2 。
对此 N=100 万,用 Chebyshev 不等式计算飞速排序所运用的可比次数超越 一千亿次的票房价值(0.1N^2)。

解答

切比雪夫不等式(Chebyshev’s inequality)
[ P(|X-mu|geq ksigma)leq
frac{1}{k^2} ]
其中,$ mu $ 代表希望,$ sigma $ 代表标准差。
对于飞速排序的可比次数来讲,$ mu = 2Nln N $ ,$ sigma=0.65N $。
(这七个结论见 2.3 节的命题 K 和命题 L)
难题中供给比较次数超越 $ 0.1N^2 $ ,能够求得 $ k $ 的值。
[ 0.65kN=0.1N^2 \ k=frac{2N}{13}
]
将 $ N=1,000,000 $ 代入
[ P(|X-27,631,021|geq
100,000,000,000)leq 0.00000000004225 ]

另请参阅

切比雪夫不等式到底是个怎么着概念? – 马同学的回复 –
乐乎

2.3.11

题目

万一在遭遇和切分成分重复的因素时大家三番八次扫描数组并非停下来,
证实使用这种艺术的高速排序在管理唯有若干种成分值的数组时运维时刻是平方级其余。

解答

唯有多少种成分值意味着大量的连年重复。
(由于存在打乱这一步骤,不设有接二连三重复的恐怕是异常的低的)
接下去大家着想那样的总是重复在退换后的快排下的习性。
1 1 1 1 1 1 1
对于如此的数组,枢轴选为 1,j 将会在 j = lo 处终止。
所以最后的结果将是每趟唯有数组的首先个要素被排序
已知每一回切分都以 O(k – 1) 的(i 和 j 都将走完全数子数组)
之所以那样的长足排序所需时间 = $ 2 (N – 1 + N – 2 + cdots + 1) = (N –
1)N $
因此对此值一样的子数组,那样的快排运维时刻是平方级其他
这正是说当数组中如此的连接重复内容越来越多,运营时刻就越临近平方等级。

2.3.12

题目

遵照代码所示轨迹的格式给出新闻量最棒的全速排序第三次是怎么着切分
数组 B A B A B A B A C A D A B R A 的。

解答

图片 6

2.3.13

题目

在顶级、平均和最坏情状下,火速排序的递归深度分别是稍稍?
那决定了系统为了跟踪递归调用所需的栈的分寸。
在最坏意况下保险递归深度为数组大小的对数级的方法请见演习 2.3.20。

解答

迅猛排序先将数组分为
(小于枢轴)枢轴(大于枢轴)三部分,然后再各自递归的排序左右两某个数组。
在那处,大家得以将很快排序的递归树看作是一棵二叉寻找树(BST, Binary
Search Tree)。
枢轴作为根结点,左子树即为左数组构造的 BST,右子树即为右数组构造的
BST。
那样难点中所求的递归深度即为所组织的 BST 的惊人。

最坏情状,每一回都独有枢轴和不仅枢轴两某个,BST 退化为链表,中度为 $ n-1
$。

最佳状态,每便枢轴都正好平分数组,构造一棵完全二叉树,中度为 $ log n
$。

平均情形,难点转化为:三个由 $ n $ 个成分随机构造的 BST
的平均中度是有个别?
《算法导论》给出的结论是 $ log n $ ,具体表达如下:
设由 $ n $ 个结点随机构成的 BST 的中度为 $ h_n $,那么有:
[ h_n=1+max(h_{l}+h_{r})
]
其中,$ h_l $ 和 $ h_r $ 分别表示左数组和右数组构造的 BST 的可观。
设枢轴地点为 $ i $,上式可简化为:
[ h_n=1+max(h_{i-1}, h_{n-i})
]
是因为枢轴地方能够在 1~n 之间自由取值且可能率相等,因而 BST
的平均中度(即中度的愿意)为:
[
E(h_n)=frac{1}{n}sum_{i=1}^{n}lbrack 1+max(h_{i-1}, h_{n-i})
rbrack ]
我们令 $ Y_n=2^{h_n} $,可得:
[ Y_n=2timesmax(Y_{i-1},Y_{n-i})
]
我们把 $ Y_n $ 代入,可得:
[ begin{align*} E(Y_n)
&=sum_{i=1}^{n}frac{1}{n}Elbrack2timesmax(Y_{i-1},
Y_{n-i})rbrack\
&=frac{2}{n}sum_{i=1}^{n}Elbrackmax(Y_{i-1},Y_{n-i})rbrack\
end{align*} ]
接下去大家去掉最大值运算,依据最大值的性质,下式分明创立:
[ Elbrackmax(X,Y)rbrackle
Elbrackmax(X,Y)+min(X,Y)rbrack=Elbrack X+Yrbrack=Elbrack
Xrbrack+Elbrack Yrbrack ]
代入可得:
[ E(Y_n)
lefrac{2}{n}sum_{i=1}^{n}(Elbrack Y_{i-1}rbrack + Elbrack
Y_{n-i} rbrack) =frac{2}{n}sum_{i=0}^{n-1}2Elbrack
Y_irbrack =frac{4}{n}sum_{i=0}^{n-1}Elbrack Y_irbrack
]
大大小小为 0 的数组构成的 BST 的惊人显然为 0,大家设 $ Y_0=0 $
。接下来用三个结缘数公式来组织上界:
[ begin{align*} 0&=Y_0=Elbrack Y_0
rbrackle
frac{1}{4}begin{pmatrix}3\3end{pmatrix}=frac{1}{4}\
1&=Y_1=Elbrack Y_1 rbracklefrac
{1}{4}begin{pmatrix}3+1\3end{pmatrix}=1 \ vdots \ Y_i
&=Elbrack
Y_irbracklefrac{1}{4}begin{pmatrix}i+3\3end{pmatrix}
end{align*} ]
专一这里的组成数公式为:
[
begin{pmatrix}n\rend{pmatrix}=frac{r!}{r!(n-r)!} ]
代入可得:
[ begin{align*} E(Y_n) &le
frac{4}{n}sum_{i=0}^{n-1}Elbrack Y_irbrack \
&lefrac{4}{n}sum_{i=0}^{n-1}frac{1}{4}begin{pmatrix}i+3\3end{pmatrix}
\
&=frac{1}{n}sum_{i=0}^{n-1}begin{pmatrix}i+3\3end{pmatrix}
end{align*} ]
接下去我们去掉求和标志,首先遵照组合数的性子,有以下等式制造
[ begin{align*}
begin{pmatrix}n\kend{pmatrix}&=begin{pmatrix}n-1\k-1end{pmatrix}+begin{pmatrix}n-1\kend{pmatrix}
\ begin{pmatrix}n\nend{pmatrix}&=1 end{align*}
]
咱俩把求和式张开获得:
[ begin{align*}
sum_{i=0}^{n-1}begin{pmatrix}i+3\3end{pmatrix}
&=begin{pmatrix}3\3end{pmatrix} +
begin{pmatrix}4\3end{pmatrix}+cdots+begin{pmatrix}n+2\3end{pmatrix}
\ &=begin{pmatrix}4\4end{pmatrix} +
begin{pmatrix}4\3end{pmatrix}+cdots+begin{pmatrix}n+2\3end{pmatrix}
\ &=begin{pmatrix}n+3\4end{pmatrix} end{align*}
]
代入可得:
[ begin{align*} E(Y_n)
&lefrac{1}{n}sum_{i=0}^{n-1}begin{pmatrix}i+3\3end{pmatrix}\
&=frac{1}{n}begin{pmatrix}n+3\4 end{pmatrix} \
&=frac{1}{n}cdotfrac{(n+3)!}{4!(n-1)!} \
&=frac{1}{4}cdotfrac{(n+3)!}{3!n!} \
&=frac{(n+1)(n+2)(n+3)}{24} \ &=frac{n^3+6n^2+11n+6}{24}
end{align*} ]
由于 (Y_n=2^{h_n}) ,因此 (Elbrack Y_n rbrack=Elbrack 2^{h_n}
rbrack)。
由于 (f(x)=2^x)
是个凸函数,能够接纳Jensen不等式(凸函数的割线一定在函数上方),即 (2^{Elbrack h_nrbrack}le Elbrack
Y_nrbrack)。
于是获得结论:
[ 2^{Elbrack h_nrbrack} le
frac{n^3+6n^2+11n+6}{24} \ Elbrack h_n rbrackle
log(frac{n^3+6n^2+11n+6}{24}) ]

另请参阅

快快排序的递归树能够算得 BST 的下结论能够在上边那个 PPT 的第 5 页找到。
QuickSort-纽约大学
《算法导论》中有关自由 BST 高度的证实(P321 西奥rem12.4)
Introduction to
Algorithms
也足以参谋下边那几个链接得到更详细的分解。
Proof that a randomly built binary search tree has logarithmic
height-StackExchange

2.3.14

题目

表明在用火速排序管理大小为 N 的不重复数组时,
正如第 i 大和第 j 大元素的概率为 2/(j – i + 1),并用该结论注脚命题 K。

解答

粤语版标题有误,详见官方修正页面:

假设 $ i < j $ 。
第一,在快捷排序中,假诺八个成分要发出沟通,意味着在那之中八个因素被选为枢轴。
还要数组中的成分各分歧样,那么四个特定的要素的相比较最多产生二遍。

那么先思考多少个特别意况,$ i = 1, j = n $
,即求最大值和最小值相比较的概率。
这时候,一旦枢轴不是那八个要素之一,
最大值和微小值会被分到多少个例外的子数组,不能够爆发相比。
所以在此种特例下第 $ i $ 大的因素和第 $ j $ 大的要素发生比较的概率为 $
frac{2}{n} = frac{2}{j-i+1} $ 。

接下去思考通常景色,假如枢轴选用了第 $ i $ 到第 $ j $ 大之外的因素,
那么第 $ i $ 大和第 $ j $
大的要素会被分到同二个子数组里,重复上述进程。
故而我们所求的票房价值只和从第 $ i $ 大到第 $ j $ 大时期的因素有关,可能率为
(frac{2}{j-i+1})。
(比如,二个箱子里有 2 个红球、1个蓝球和 7
个白球,现在摸球而不放回。
假设摸到白球能够再摸贰回,直到摸到红球或蓝球截止。
肯定在这里样的平整下摸到红球或蓝球的概率为 1,即白球对可能率未有影响。)

近些日子大家曾经收获了某七个成分比较的可能率 (E(X_{ij})),接下去大家求每四个因素相比较的概率$ E(X) $。
[ begin{align*} E(X) &=
sum_{i=1}^{n}sum_{j=i+1}^{n}E(X_{ij})\
&=sum_{i=1}^{n}2(frac{1}{2}+frac{1}{3}+cdots+frac{1}{n-i+1})
\ &=2n(frac{1}{2}+frac{1}{3}+cdots+frac{1}{n-i+1})
end{align*} ]
据书上说调养级数的天性($ ln (n) < 1+ frac{1}{2}+ cdots +
frac{1}{n} < 1+ln(n) $),可以获得结论:
[ E(X) le 2n ln(n) ]

另请参阅

上边这些链接里的 3.4.2 节给出领悟法。
lect0906 –
卡内基梅隆大学
一经依然不能够精通为啥屡屡切分不影响可能率,可以参照三门难点的解释:
蒙提霍尔难点 –
维基百科
蒙提霍尔难点(又称三门主题素材、湖羊汽车难点)的正解是怎么?-
乐乎

2.3.15

题目

螺丝钉和螺帽。(G.J.E.Rawlins)
假诺有 N 个螺丝和 N 个螺帽混在一批,你供给火速将它们配成对。
二个螺丝只会同盟叁个螺帽,一个螺帽也只会合营一个螺钉。
您能够试着把贰个螺钉和一个螺帽拧在联合造访哪个人大了,但无法直接比较八个螺丝或然八个螺帽。
交给多个减轻那一个难点的得力措施。

解答

实则只必要修改快速排序的切分方法,分五次举办切分。
率先选第一个螺母作为枢轴,找到呼应的螺丝($ O(n)
$)放到第一人,对螺丝数组举办切分。
接下来再用找到的螺丝对螺母数组实行切分。

螺母类,完结了对螺丝类的 IComparable 接口

/// <summary>
/// 螺母类。
/// </summary>
public class Nut<T> : IComparable<Bolt<T>> where T : IComparable<T>
{
    /// <summary>
    /// 螺母的值。
    /// </summary>
    public T Value { get; set; }

    /// <summary>
    /// 螺母的构造函数。
    /// </summary>
    /// <param name="value">螺母的值。</param>
    public Nut(T value) => this.Value = value;

    /// <summary>
    /// 比较方法,螺母只能和螺丝比较。
    /// </summary>
    /// <param name="other">需要比较的螺丝。</param>
    /// <returns></returns>
    public int CompareTo(Bolt<T> other)
    {
        return this.Value.CompareTo(other.Value);
    }
}

接近的有螺丝类。

/// <summary>
/// 螺丝类。
/// </summary>
public class Bolt<T> : IComparable<Nut<T>> where T : IComparable<T>
{
    /// <summary>
    /// 螺丝的值。
    /// </summary>
    public T Value { get; set; }

    /// <summary>
    /// 螺丝的默认构造函数。
    /// </summary>
    /// <param name="value">螺丝的值。</param>
    public Bolt(T value) => this.Value = value;

    /// <summary>
    /// 比较方法,螺丝只能和螺母比较。
    /// </summary>
    /// <param name="other">需要比较的螺母。</param>
    /// <returns></returns>
    public int CompareTo(Nut<T> other)
    {
        return this.Value.CompareTo(other.Value);
    }
}
代码

修改后的排序方法。

using System;

namespace _2._3._15
{
    /// <summary>
    /// 用快排的方式解决螺母和螺帽的问题。
    /// </summary>
    public class BoltsAndNuts
    {
        private readonly Random random = new Random();

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public BoltsAndNuts() { }

        /// <summary>
        /// 对螺丝和螺母排序。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        public void Sort<T>(Bolt<T>[] bolts, Nut<T>[] nuts) where T : IComparable<T>
        {
            if (bolts.Length != nuts.Length)
                throw new ArgumentException("数组长度必须一致");

            Shuffle(bolts);
            Shuffle(nuts);
            Sort(bolts, nuts, 0, bolts.Length - 1);
        }

        /// <summary>
        /// 对螺丝和螺母排序。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        /// <param name="lo">起始下标。</param>
        /// <param name="hi">终止下标。</param>
        public void Sort<T>(Bolt<T>[] bolts, Nut<T>[] nuts, int lo, int hi) where T : IComparable<T>
        {
            if (hi <= lo)
                return;
            int j = Partition(bolts, nuts, lo, hi);
            Sort(bolts, nuts, lo, j - 1);
            Sort(bolts, nuts, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        /// <param name="lo">起始下标。</param>
        /// <param name="hi">终止下标。</param>
        /// <returns>切分位置。</returns>
        private int Partition<T>(Bolt<T>[] bolts, Nut<T>[] nuts, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            Bolt<T> pivotB = bolts[lo];
            // 找到对应螺丝
            for (int k = lo; k <= hi; k++)
            {
                if (nuts[k].CompareTo(pivotB) == 0)
                {
                    Exch(nuts, k, lo);
                    break;
                }
            }
            // 先用螺母去套螺丝
            while (true)
            {
                while (nuts[++i].CompareTo(pivotB) < 0)
                    if (i == hi)
                        break;
                while (pivotB.CompareTo(nuts[--j]) < 0)
                    if (j == lo)
                        break;

                if (i >= j)
                    break;
                Exch(nuts, i, j);
            }
            Exch(nuts, lo, j);

            // 再用螺丝去比较螺母
            Nut<T> pivotN = nuts[j];
            i = lo;
            j = hi + 1;
            while (true)
            {
                while (bolts[++i].CompareTo(pivotN) < 0)
                    if (i == hi)
                        break;
                while (pivotN.CompareTo(bolts[--j]) < 0)
                    if (j == lo)
                        break;

                if (i >= j)
                    break;

                Exch(bolts, i, j);
            }
            Exch(bolts, lo, j);

            return j;
        }

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

        /// <summary>
        /// 交换两个元素。
        /// </summary>
        /// <typeparam name="T">元素类型。</typeparam>
        /// <param name="a">需要交换的第一个元素。</param>
        /// <param name="b">需要交换的第二个元素。</param>
        private void Exch<T>(T[] a, int lo, int hi)
        {
            T t = a[lo];
            a[lo] = a[hi];
            a[hi] = t;
        }
    }
}
另请参阅

下边这一个网址提交了那道题的解法,还提交了另一种光天化日算法(非随机的算法)的舆论链接。
Matching Nuts and Bolts –
Solution

2.3.16

题目

最棒状态。
编排一段程序来生成使算法 2.5 中的 sort()
方法表现最好的数组(无重复成分):
数组大小为 N 且不带有重复元素,每回切分后八个子数组的深浅最多差 1
(子数组的大小与满含 N 个一律成分的数组的切分景况相同)。
(对于那道练习,大家无需在排序起先时打乱数组。)

解答

合法完毕见:

类似于高效排序的布局,只要中式茶食的两侧都以拔尖状态,那么一切数组正是拔尖状态了。
具体方法是:
首先构造四个长期以来数组,
然后找到中式茶食(作为枢轴),
对中央左右两边子数组进行布局,
将甄选的枢轴放到以前处(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

2.3.17

题目

哨兵。
修改算法 2.5,去掉内循环 while 中的边界检查。
是因为切分成分本人正是二个哨兵(v 不容许低于
a[lo]),左侧面界检查是剩下的。
要去掉另二个反省,能够在打乱数组后将数组的最大因素方法 a[length – 1]
中。
该因素永恒不会移动(除非和非凡的成分沟通),能够在有着包括它的子数组中形成哨兵。
只顾:在处理内部子数组时,右子数组中最侧面的成分得以充作左子数组侧面界的哨兵。

解答

鲁人持竿题意修改代码就能够,在调用 Suffle()
之后增加一段用于寻觅最大值的不二秘技($ O(n) $)。

/// <summary>
/// 用快速排序对数组 a 进行升序排序。
/// </summary>
/// <typeparam name="T">需要排序的类型。</typeparam>
/// <param name="a">需要排序的数组。</param>
public override void Sort<T>(T[] a)
{
    Shuffle(a);

    // 把最大元素放到最后一位
    int maxIndex = 0;
    for (int i = 0; i < a.Length; i++)
    {
        if (Less(a[maxIndex], a[i]))
            maxIndex = i;
    }
    Exch(a, maxIndex, a.Length - 1);

    Sort(a, 0, a.Length - 1);
    Debug.Assert(IsSorted(a));
}
代码

修改后的迅猛排序类。

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._17
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortX : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortX() { }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);

            // 把最大元素放到最后一位
            int maxIndex = 0;
            for (int i = 0; i < a.Length; i++)
            {
                if (Less(a[maxIndex], a[i]))
                    maxIndex = i;
            }
            Exch(a, maxIndex, a.Length - 1);

            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;
            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;
            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;
        }

        /// <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._17
{
    /*
     * 2.3.17
     * 
     * 哨兵。
     * 修改算法 2.5,去掉内循环 while 中的边界检查。
     * 由于切分元素本身就是一个哨兵(v 不可能小于 a[lo]),
     * 左侧边界检查是多余的。
     * 要去掉另一个检查,可以在打乱数组后将数组的最大元素方法 a[length - 1] 中。
     * 该元素永远不会移动(除非和相等的元素交换),
     * 可以在所有包含它的子数组中成为哨兵。
     * 注意:在处理内部子数组时,
     * 右子数组中最左侧的元素可以作为左子数组右边界的哨兵。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quick = new QuickSort();
            QuickSortX quickSortX = new QuickSortX();
            int arrayLength = 1000000;
            int[] a = SortCompare.GetRandomArrayInt(arrayLength);
            int[] b = new int[arrayLength];
            a.CopyTo(b, 0);

            double time1 = SortCompare.Time(quick, a);
            double time2 = SortCompare.Time(quickSortX, b);
            Console.WriteLine("QSorttQSort with Sentinelst");
            Console.WriteLine(time1 + "t" + time2 + "t");
        }
    }
}
另请参阅

Quick

2.3.18

题目

三取样切分。
为高效排序实现正文所述的三取样切分(参见 2.3.3.2
节)。运维双倍测量检验来认同那项退换的功能。

解答

历次切分时都取前四个要素的中位数作为枢轴,那足以拉动约 5%~一成的质量升高。
此地透过三回比较将前多少个数排序,然后把多少个数中的中位数放到数组开始,最大值放到数组末尾。
最大值被平放了最终,枢轴一点都不大概超乎末尾的这些数,由此左边界决断能够去掉。
再正是鉴于枢轴不或然低于自己,由此左侧界推断也得以去掉。
这么就足以把切分中的五个边界判定任何去掉了。
终极对于大小为 2 的数组做特殊管理,通过一遍相比较直接排序并再次回到。

测量检验结果:
图片 7

代码

QuickSortMedian3

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._18
{
    /// <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)
            {
                if (Less(a[hi], a[lo]))
                    Exch(a, lo, hi);

                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._18
{
    /*
     * 2.3.18
     * 
     * 三取样切分。
     * 为快速排序实现正文所述的三取样切分(参见 2.3.3.2 节)。
     * 运行双倍测试来确认这项改动的效果。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quickNormal = new QuickSort();
            QuickSortMedian3 quickMedian = new QuickSortMedian3();
            int arraySize = 200000;                         // 初始数组大小。
            const int trialTimes = 4;                       // 每次实验的重复次数。
            const int trialLevel = 5;                       // 双倍递增的次数。

            Console.WriteLine("ntmediantnormaltratio");
            for (int i = 0; i < trialLevel; i++)
            {
                double timeMedian = 0;
                double timeNormal = 0;
                for (int j = 0; j < trialTimes; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(arraySize);
                    int[] b = new int[a.Length];
                    a.CopyTo(b, 0);
                    timeNormal += SortCompare.Time(quickNormal, b);
                    timeMedian += SortCompare.Time(quickMedian, a);

                }
                timeMedian /= trialTimes;
                timeNormal /= trialTimes;
                Console.WriteLine(arraySize + "t" + timeMedian + "t" + timeNormal + "t" + timeMedian / timeNormal);
                arraySize *= 2;
            }
        }
    }
}
另请参阅

Quick

2.3.19

题目

五取样切分。
完毕一种基于随机收取子数组中 5 个要素并取中位数举办切分的高速排序。
将取样成分放在数组的旁边以保障独有中位数成分加入了切分。
运营双倍测量试验来分明那项改造的功能,并和标准的飞跃排序以致三取样的飞跃排序(请见上一道练习)举行相比较。
附加题:找到一种对于自由输入都只须求轻便 7 次比较的五取样算法。

解答

重视介绍一下以此点儿七遍比较的五取样算法。
率先要是多少个数字为 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 放到数组的最终作为哨兵,去掉侧面界的论断。
还要让左右两边指针都向中档移动两位,减少不须要的可比。

测量检验结果,相比较普通快排质量进步约 百分之十,和三取样快排差异非常小。
图片 8

代码

五取样快排

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("ntmedian5tmedian3tnormaltmedian5/normalttmedian5/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#

2.3.20

题目

非递归的急忙排序。
兑现三个非递归的相当慢排序,使用贰个循环来将弹出栈的子数组切分并将结果子数组重新压入栈。
留神:先将很大的子数组压入栈,这样就足以确认保障栈最八只会有 lgN 个因素。

解答

实则正是用一个栈保存每一次切分后的子数组下标。
重在代码如下,这里运用的栈(链栈)是在 1.3 中塑造的:

/// <summary>
/// 用快速排序对数组 a 进行升序排序。
/// </summary>
/// <typeparam name="T">需要排序的类型。</typeparam>
/// <param name="a">需要排序的数组。</param>
public override void Sort<T>(T[] a)
{
    Shuffle(a);
    Stack<int> stack = new Stack<int>();
    stack.Push(0);
    stack.Push(a.Length - 1);

    while (!stack.IsEmpty())
    {
        // 压入顺序是先 lo,再 hi,故弹出顺序是先 hi 再 lo
        int hi = stack.Pop();
        int lo = stack.Pop();

        if (hi <= lo)
            continue;

        int j = Partition(a, lo, hi);

        // 让较大的子数组先入栈(先排序较小的子数组)
        if (j - lo > hi - j)
        {
            stack.Push(lo);
            stack.Push(j - 1);

            stack.Push(j + 1);
            stack.Push(hi);
        }
        else
        {
            stack.Push(j + 1);
            stack.Push(hi);

            stack.Push(lo);
            stack.Push(j - 1);
        }
    }
    Debug.Assert(IsSorted(a));
}

由于栈操作比函数调用操作消耗费时间间更加长,因而测量检验后的结果会比原本快排慢 百分之三十左右。
图片 9

代码

QuickSortNonRecursive

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._20
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortNonRecursive : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortNonRecursive() { }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);
            Stack<int> stack = new Stack<int>();
            stack.Push(0);
            stack.Push(a.Length - 1);

            while (!stack.IsEmpty())
            {
                // 压入顺序是先 lo,再 hi,故弹出顺序是先 hi 再 lo
                int hi = stack.Pop();
                int lo = stack.Pop();

                if (hi <= lo)
                    continue;

                int j = Partition(a, lo, hi);

                // 让较大的子数组先入栈(先排序较小的子数组)
                if (j - lo > hi - j)
                {
                    stack.Push(lo);
                    stack.Push(j - 1);

                    stack.Push(j + 1);
                    stack.Push(hi);
                }
                else
                {
                    stack.Push(j + 1);
                    stack.Push(hi);

                    stack.Push(lo);
                    stack.Push(j - 1);
                }
            }
            Debug.Assert(IsSorted(a));
        }

        /// <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;
            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;
        }

        /// <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._20
{
    /*
     * 2.3.20
     * 
     * 非递归的快速排序。
     * 实现一个非递归的快速排序,
     * 使用一个循环来将弹出栈的子数组切分并将结果子数组重新压入栈。
     * 注意:
     * 先将较大的子数组压入栈,这样就可以保证栈最多只会有 lgN 个元素。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quickNormal = new QuickSort();
            QuickSortNonRecursive quickNonRecursive = new QuickSortNonRecursive();
            int arraySize = 200000;                         // 初始数组大小。
            const int trialTimes = 4;                       // 每次实验的重复次数。
            const int trialLevel = 5;                       // 双倍递增的次数。

            Console.WriteLine("ntnon-recursivetnormaltratio");
            for (int i = 0; i < trialLevel; i++)
            {
                double timeRecursive = 0;
                double timeNormal = 0;
                for (int j = 0; j < trialTimes; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(arraySize);
                    int[] b = new int[a.Length];
                    a.CopyTo(b, 0);
                    timeNormal += SortCompare.Time(quickNormal, b);
                    timeRecursive += SortCompare.Time(quickNonRecursive, a);

                }
                timeRecursive /= trialTimes;
                timeNormal /= trialTimes;
                Console.WriteLine(arraySize + "t" + timeRecursive + "tt" + timeNormal + "t" + timeRecursive / timeNormal);
                arraySize *= 2;
            }
        }
    }
}

用到的栈的落到实处

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace _2._3._20
{
    /// <summary>
    /// 栈类。
    /// </summary>
    /// <typeparam name="Item">栈中存放的元素类型。</typeparam>
    public class Stack<Item> : IEnumerable<Item>
    {
        private Node<Item> first;
        private int count;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public Stack()
        {
            this.first = null;
            this.count = 0;
        }

        /// <summary>
        /// 复制构造函数。
        /// </summary>
        /// <param name="s"></param>
        public Stack(Stack<Item> s)
        {
            if (s.first != null)
            {
                this.first = new Node<Item>(s.first);
                for (Node<Item> x = this.first; x.next != null; x = x.next)
                {
                    x.next = new Node<Item>(x.next);
                }
            }
            this.count = s.count;
        }

        /// <summary>
        /// 检查栈是否为空。
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return this.first == null;
        }

        /// <summary>
        /// 返回栈内元素的数量。
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.count;
        }

        /// <summary>
        /// 将一个元素压入栈中。
        /// </summary>
        /// <param name="item">要压入栈中的元素。</param>
        public void Push(Item item)
        {
            Node<Item> oldFirst = this.first;
            this.first = new Node<Item>();
            this.first.item = item;
            this.first.next = oldFirst;
            this.count++;
        }

        /// <summary>
        /// 将一个元素从栈中弹出,返回弹出的元素。
        /// </summary>
        /// <returns></returns>
        public Item Pop()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Stack Underflow");
            Item item = this.first.item;
            this.first = this.first.next;
            this.count--;
            return item;
        }

        /// <summary>
        /// 返回栈顶元素(但不弹出它)。
        /// </summary>
        /// <returns></returns>
        public Item Peek()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Stack Underflow");
            return this.first.item;
        }

        /// <summary>
        /// 将两个栈连接。
        /// </summary>
        /// <param name="s1">第一个栈。</param>
        /// <param name="s2">第二个栈(将被删除)。</param>
        /// <returns></returns>
        public static Stack<Item> Catenation(Stack<Item> s1, Stack<Item> s2)
        {
            if (s1.IsEmpty())
            {
                s1.first = s2.first;
                s1.count = s2.count;
            }
            else
            {
                Node<Item> last = s1.first;
                while (last.next != null)
                {
                    last = last.next;
                }
                last.next = s2.first;
                s1.count += s2.count;
            }
            s2 = null;
            return s1;
        }

        /// <summary>
        /// 创建栈的浅表副本。
        /// </summary>
        /// <returns></returns>
        public Stack<Item> Copy()
        {
            Stack<Item> temp = new Stack<Item>();
            temp.first = this.first;
            temp.count = this.count;
            return temp;
        }

        public override string ToString()
        {
            StringBuilder s = new StringBuilder();
            foreach (Item n in this)
            {
                s.Append(n);
                s.Append(' ');
            }
            return s.ToString();
        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new StackEnumerator(this.first);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        private class StackEnumerator : IEnumerator<Item>
        {
            private Node<Item> current;
            private Node<Item> first;

            public StackEnumerator(Node<Item> first)
            {
                this.current = new Node<Item>();
                this.current.next = first;
                this.first = this.current;
            }

            Item IEnumerator<Item>.Current => this.current.item;

            object IEnumerator.Current => this.current.item;

            void IDisposable.Dispose()
            {
                this.current = null;
                this.first = null;
            }

            bool IEnumerator.MoveNext()
            {
                if (this.current.next == null)
                    return false;

                this.current = this.current.next;
                return true;
            }

            void IEnumerator.Reset()
            {
                this.current = this.first;
            }
        }
    }
}
另请参阅

Quick

Generics

2.3.21

题目

将再一次成分排序的相比次数的下界。
做到命题 M 的表明的率先片段。
参照他事他说加以考察命题 I 的认证并留意当有 $ k $ 个主键值时全数因素存在 $
N!/f_1!f_2!…f_k!$ 种不一致的排列,
当中第 $ i $ 个主键值出现的概率为 $ f_1 $(即 $ N_{p_i} $,遵照命题 M
的记法),且 $ f_1+… +f_k=N $。

解答

先是引入命题 I
的定论,对于互不一致的主键值,基于比较的排序算法的下界等于所产生的可比树的可观,即:
[ h ge log_2{N!} ]
那么大家题目就可以转接为注脚
[ h ge log_2
(frac{N!}{f_1!f_2!cdots f_k!}) ge log_2 N! ]
这里的 $ f_i $ 为某个主键值出现的作用,即有些主键值现身的次数,由此
(f_ige 1) 。
听他们说难点给出的规范,假使主键互不重复,此时 $ k=N $,且 $
f_1=f_2=cdots=f_k=1 $ 。
那么 $ f_1!f_2!cdots f_k!=1 $ ,待证式子即为命题 I 的结论。

那么当主键有双重时,此时 $ k < N $,为使 $ f_1+f_2+ cdots +
f_k=N $ ,起码存在贰个 $ f_m ge 2 $。
故此时:
[ f_1!f_2!cdots f_k!
>1Rightarrow frac{N!}{f_1!f_2!cdots f_k!}<N! Rightarrow
\ h ge log_2 (frac{N!}{f_1!f_2!cdots f_k!}) ge log_2
N! blacksquare ]
得证。

另请参阅

lower bounds of sorting-The University of
Maryland

2.3.22

题目

十分的快三向切分。(J.Bently,D.McIlroy)
用将另行成分放置于子数组两端的格局得以完毕二个音信量最优的排序算法。
运用七个索引 p 和 q,使得 a[lo…p-1] 和 a[q+1..hi] 的因素都和
a[lo] 相等。
使用其余八个索引 i 和 j,使得 a[p…i-1] 小于 a[lo],a[j+i..q]
大于 a[lo]。
在内循环中投入代码,在 a[i] 和 v 相等时将其与 a[p] 交换(并将 p 加
1),
在 a[j] 和 v 相等且 a[i] 和 a[j] 尚未和 v 进行相比较前边将其与
a[q] 交换。
加多在切分循环甘休后将和 v 相等的要素交流到正确地方的代码,如图 2.3.6
所示。
请注意:
那边达成的代码和正文中提交的代码时等价的,
因为此地额外的置换用于和切分成分相等的因素,
而本文中的代码将万分的调换用于和切分成分不等的要素。

解答

合法实现见:

迅猛三向切分

舆论援引见「另请参阅」部分。
算法演示
图片 10

Ninther 算法

官方实现中用到了 Ninther 算法用于采用近似中位数(作为枢轴),
该算法由 John Tukey 在 一九八〇 年提议,诗歌援引见「另请参阅」部分。
这一个算法的思量实际很简短,假使我们有七个数 $ y_1, y_2, y_3 $
,那么内部位数为:
[ y_A= {rm median}lbrace
y_1,y_2,y_3 rbrace ]
现今对于八个数,大家以多少个为一组,取四此中位数:
[ y_A= {rm median}lbrace
y_1,y_2,y_3 rbrace \ y_B= {rm median}lbrace y_4,y_5,y_6
rbrace \ y_C= {rm median}lbrace y_7,y_8,y_9 rbrace
]
接下去取那八当中位数的中位数,有:
[ y_E= {rm median}lbrace
y_A,y_B,y_C rbrace ]
我们把上述进程封装成函数,即 $ y_E= {rm ninther}lbrace
y_1,y_2,cdots,y_9 rbrace $ 。
于是乎大家赢得的 $ y_E $ 即为近似中位数,如若 $ lbrace
y_1,y_2,cdots,y_9 rbrace $ 是干燥数列,那么 $ y_E $ 正是中位数。

收获四个数中的中位数

实在,大家能够直接画出八个数排列的具备希望,得到决策树。
图片 11
下一场根据决策树写出取中位数的算法:

private int Median3<T>(T[] a, int i, int j, int k) where T : IComparable<T>
{
    return
        (Less(a[i], a[j]) ?
        (Less(a[j], a[k]) ? j : Less(a[i], a[k]) ? k : i) :
        (Less(a[k], a[j]) ? j : Less(a[k], a[i]) ? k : i));
}

测验结果

巩固约 五分二 左右的性质。
图片 12

代码

QuickBentleyMcIlroy

using System;
using System.Diagnostics;

namespace Quick
{
    public class QuickBentleyMcIlroy : BaseSort
    {
        /// <summary>
        /// 小于这个数值的数组调用插入排序。
        /// </summary>
        private readonly int INSERTION_SORT_CUTOFF = 8;

        /// <summary>
        /// 小于这个数值的数组调用中位数作为枢轴。
        /// </summary>
        private readonly int MEDIAN_OF_3_CUTOFF = 40;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickBentleyMcIlroy() { }

        /// <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>
        /// 对指定范围内的数组进行排序。
        /// </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>
        {
            int n = hi - lo + 1;

            if (n <= this.INSERTION_SORT_CUTOFF)
            {
                InsertionSort(a, lo, hi);
                return;
            }
            else if (n <= this.MEDIAN_OF_3_CUTOFF)
            {
                // 对于较小的数组,直接选择左中右三个元素中的中位数作为枢轴。
                int m = Median3(a, lo, lo + n / 2, hi);
                Exch(a, m, lo);
            }
            else
            {
                // 对于较大的数组使用 Turkey Ninther 作为枢轴。
                int eps = n / 8;
                int mid = lo + n / 2;
                int m1 = Median3(a, lo, lo + eps, lo + eps + eps);
                int m2 = Median3(a, mid - eps, mid, mid + eps); 
                int m3 = Median3(a, hi - eps - eps, hi - eps, hi);
                int ninther = Median3(a, m1, m2, m3);
                Exch(a, ninther, lo);
            }

            // 三向切分
            int i = lo, j = hi + 1;
            int p = lo, q = hi + 1;
            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 && IsEqual(a[i], v))
                    Exch(a, ++p, i);
                if (i >= j)
                    break;

                Exch(a, i, j);
                if (IsEqual(a[i], v))
                    Exch(a, ++p, i);
                if (IsEqual(a[j], v))
                    Exch(a, --q, j);
            }

            i = j + 1;
            for (int k = lo; k <= p; k++)
                Exch(a, k, j--);
            for (int k = hi; k >= q; k--)
                Exch(a, k, i++);

            Sort(a, lo, j);
            Sort(a, i, hi);
        }

        /// <summary>
        /// 判断两个元素是否值相等。
        /// </summary>
        /// <typeparam name="T">需要判断的元素类型。</typeparam>
        /// <param name="a">进行比较的第一个元素。</param>
        /// <param name="b">进行比较的第二个元素。</param>
        /// <returns>两个元素的值是否相等。</returns>
        private bool IsEqual<T>(T a, T b) where T : IComparable<T>
        {
            return a.CompareTo(b) == 0;
        }

        /// <summary>
        /// 用插入排序对指定范围内的数组排序。
        /// </summary>
        /// <typeparam name="T">数组的元素类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序的起始下标。</param>
        /// <param name="hi">排序的终止下标。</param>
        private void InsertionSort<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            for (int i = lo; i <= hi; i++)
            {
                for (int j = i; j > lo && Less(a[j], a[j - 1]); j--)
                {
                    Exch(a, j, j - 1);
                }
            }
        }

        /// <summary>
        /// 获取三个元素中的中位数。
        /// </summary>
        /// <typeparam name="T">用于排序的元素。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="i">第一个待选元素的下标。</param>
        /// <param name="j">第二个待选元素的下标。</param>
        /// <param name="k">第三个待选元素的下标。</param>
        /// <returns></returns>
        private int Median3<T>(T[] a, int i, int j, int k) where T : IComparable<T>
        {
            return
               (Less(a[i], a[j]) ?
               (Less(a[j], a[k]) ? j : Less(a[i], a[k]) ? k : i) :
               (Less(a[k], a[j]) ? j : Less(a[k], a[i]) ? k : i));
        }
    }
}

测量检验用例

using System;
using Quick;

namespace _2._3._22
{
    /*
     * 2.3.22
     * 
     * 快速三向切分。(J.Bently,D.McIlroy)
     * 用将重复元素放置于子数组两端的方式实现一个信息量最优的排序算法。
     * 使用两个索引 p 和 q,使得 a[lo...p-1] 和 a[q+1..hi] 的元素都和 a[lo] 相等。
     * 使用另外两个索引 i 和 j,
     * 使得 a[p...i-1] 小于 a[lo],a[j+i..q] 大于 a[lo]。
     * 在内循环中加入代码,在 a[i] 和 v 相当时将其与 a[p] 交换(并将 p 加 1),
     * 在 a[j] 和 v 相等且 a[i] 和 a[j] 尚未和 v 进行比较之前将其与 a[q] 交换。
     * 添加在切分循环结束后将和 v 相等的元素交换到正确位置的代码,如图 2.3.6 所示。
     * 请注意:
     * 这里实现的代码和正文中给出的代码时等价的,
     * 因为这里额外的交换用于和切分元素相等的元素,
     * 而正文中的代码将额外的交换用于和切分元素不等的元素。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quickNormal = new QuickSort();
            QuickBentleyMcIlroy quickBentleyMcIlroy = new QuickBentleyMcIlroy();
            int arraySize = 800000;                         // 初始数组大小。
            const int trialTimes = 1;                       // 每次实验的重复次数。
            const int trialLevel = 8;                       // 双倍递增的次数。

            Console.WriteLine("ntt3waytnormaltratio");
            for (int i = 0; i < trialLevel; i++)
            {
                double timeBentleyMcIlroy = 0;
                double timeNormal = 0;
                for (int j = 0; j < trialTimes; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(arraySize);
                    int[] b = new int[a.Length];
                    a.CopyTo(b, 0);
                    timeNormal += SortCompare.Time(quickNormal, b);
                    timeBentleyMcIlroy += SortCompare.Time(quickBentleyMcIlroy, a);

                }
                timeBentleyMcIlroy /= trialTimes;
                timeNormal /= trialTimes;
                if (arraySize < 10000000)
                    Console.WriteLine(arraySize + "tt" + timeBentleyMcIlroy + "t" + timeNormal + "t" + timeBentleyMcIlroy / timeNormal);
                else
                    Console.WriteLine(arraySize + "t" + timeBentleyMcIlroy + "t" + timeNormal + "t" + timeBentleyMcIlroy / timeNormal);
                arraySize *= 2;
            }
        }
    }
}
另请参阅

关于这种火速排序算法的来源于以至多个数的中位数的选用算法,请参阅上边那篇
1993 年的诗歌:
Bentley J L, McIlroy M D. Engineering a sort function[J]. Software:
Practice and Experience, 1993, 23(11):
1249-1265.
下边这份 2004 年的 PPT 详细分解和深入分析了法定完结代码的思绪和品质:
Sedgewick R, Bentley J. Quicksort is optimal[J]. Knuthfest, Stanford
University, Stanford,
2002.
有关选拔中位数 Ninther 算法,请参阅上面那篇 1980 年的散文:
Tukey J W. The ninther, a technique for low-effort robust (resistant)
location in large samples[M]//Contributions to Survey Sampling and
Applied Statistics. 1978:
251-257.
以致依照规矩给出本题用到的类库链接:
Quick

2.3.23

题目

Java 的排序库函数。
在练习 2.3.22 的代码中利用 Tukey’s ninther
方法来寻找切分成分——选用三组,
每组四个要素,分别取三组成分的中位数,然后取四其中位数的中位数作为切分元素,
且在排序小数组时切换来插入排序。

解答

官方实现见:
见 2.3.22 的解答,在那之中已经满含了这个改动。

代码

QuickBentleyMcIlroy

using System;
using System.Diagnostics;

namespace Quick
{
    public class QuickBentleyMcIlroy : BaseSort
    {
        /// <summary>
        /// 小于这个数值的数组调用插入排序。
        /// </summary>
        private readonly int INSERTION_SORT_CUTOFF = 8;

        /// <summary>
        /// 小于这个数值的数组调用中位数作为枢轴。
        /// </summary>
        private readonly int MEDIAN_OF_3_CUTOFF = 40;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickBentleyMcIlroy() { }

        /// <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>
        /// 对指定范围内的数组进行排序。
        /// </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>
        {
            int n = hi - lo + 1;

            if (n <= this.INSERTION_SORT_CUTOFF)
            {
                InsertionSort(a, lo, hi);
                return;
            }
            else if (n <= this.MEDIAN_OF_3_CUTOFF)
            {
                // 对于较小的数组,直接选择左中右三个元素中的中位数作为枢轴。
                int m = Median3(a, lo, lo + n / 2, hi);
                Exch(a, m, lo);
            }
            else
            {
                // 对于较大的数组使用 Turkey Ninther 作为枢轴。
                int eps = n / 8;
                int mid = lo + n / 2;
                int m1 = Median3(a, lo, lo + eps, lo + eps + eps);
                int m2 = Median3(a, mid - eps, mid, mid + eps); 
                int m3 = Median3(a, hi - eps - eps, hi - eps, hi);
                int ninther = Median3(a, m1, m2, m3);
                Exch(a, ninther, lo);
            }

            // 三向切分
            int i = lo, j = hi + 1;
            int p = lo, q = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v)) ;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;

                if (i == j && IsEqual(a[i], v))
                    Exch(a, ++p, i);
                if (i >= j)
                    break;

                Exch(a, i, j);
                if (IsEqual(a[i], v))
                    Exch(a, ++p, i);
                if (IsEqual(a[j], v))
                    Exch(a, --q, j);
            }

            i = j + 1;
            for (int k = lo; k <= p; k++)
                Exch(a, k, j--);
            for (int k = hi; k >= q; k--)
                Exch(a, k, i++);

            Sort(a, lo, j);
            Sort(a, i, hi);
        }

        /// <summary>
        /// 判断两个元素是否值相等。
        /// </summary>
        /// <typeparam name="T">需要判断的元素类型。</typeparam>
        /// <param name="a">进行比较的第一个元素。</param>
        /// <param name="b">进行比较的第二个元素。</param>
        /// <returns>两个元素的值是否相等。</returns>
        private bool IsEqual<T>(T a, T b) where T : IComparable<T>
        {
            return a.CompareTo(b) == 0;
        }

        /// <summary>
        /// 用插入排序对指定范围内的数组排序。
        /// </summary>
        /// <typeparam name="T">数组的元素类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序的起始下标。</param>
        /// <param name="hi">排序的终止下标。</param>
        private void InsertionSort<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            for (int i = lo; i <= hi; i++)
            {
                for (int j = i; j > lo && Less(a[j], a[j - 1]); j--)
                {
                    Exch(a, j, j - 1);
                }
            }
        }

        /// <summary>
        /// 获取三个元素中的中位数。
        /// </summary>
        /// <typeparam name="T">用于排序的元素。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="i">第一个待选元素的下标。</param>
        /// <param name="j">第二个待选元素的下标。</param>
        /// <param name="k">第三个待选元素的下标。</param>
        /// <returns></returns>
        private int Median3<T>(T[] a, int i, int j, int k) where T : IComparable<T>
        {
            return
               (Less(a[i], a[j]) ?
               (Less(a[j], a[k]) ? j : Less(a[i], a[k]) ? k : i) :
               (Less(a[k], a[j]) ? j : Less(a[k], a[i]) ? k : i));
        }
    }
}
另请参阅

Quick

2.3.24

题目

抽样排序。(W.Frazer,A.McKellar)
万事如意一个高速排序,取样大小为 2^k-1。
第一将取样获得的因素排序,然后在递归函数中使用样板的中位数切分。
分为两有的的另外样板成分不须求另行排序并能够分级采取于原数组的多个子数组。
这种算法称为取样排序。

解答

抽样排序的主见异常的粗略:
好端端快排的枢轴唯有一个。
一旦用三个数组来充作枢轴,依据相排版序地点的不一致自动选取相应的枢轴,
显著能够更加好的推断中位数,以求更加好的切分效果。
于是乎引进了「取样」的概念,尽管我们从源数组中随机取了 3
个成分并对其排序,
那么那 3
个成分的中位数能够看做第三次切分的枢轴,剩余多少个要素则能够出任切分后多少个子数组的枢轴。
那么当取样成分达到三个老少咸宜的数码时,就能够达到规定的规范进步切分功用的对象。

粗粗思路如下:
首先先从输入数组里随机取一些因素,作为「取样数组」。
用随机排序算法(譬如快排)对取样数组举办排序。
(由于取样数组常常都不大,这一步的时辰开支平日不会耳熟能详属性)
抽取取样数组里面包车型地铁中位数,充当枢轴对余下的数组举办切分。
自此的切分中,依照相排版序区间在剩余数组中的相对地点,
用取样数组中对应位置的数作为枢轴,直到一切排序达成。

杂谈里关系了二种达成方式。
首先种方法
抽样数组和剩余数组是分手保存的。
历次切分达成后,并不把枢轴放入剩余数组中,
而是等到剩余数组全体排序完结之后再用三次归并(merge)操作将取样数组和剩余数组归并。
第三种办法
抽样数组和剩余数组保存在一样片空间里,那也是那份题解所完毕的方式。
图片 13
在打乱输入数组之后,取前 2^k-1 个成分作为取样数组,用快排对其排序。
然后把取样数组的后半有的放到任何数组的末梢。
那般操作的结果是输入数组分为了多个部分:
稳步的取样数组、取样数组的中位数、冬辰的剩余数组、有序的抽样数组。
中位数则放在第一片段的最后,我们将其看作枢轴对剩余数组进行切分,数组变为:
有序的抽样数组、小于中位数的有个别、枢轴、大于中位数的有个别、有序的取样数组
接下去我们再对第二个部分取半,放到中位数早前;对最终一部分取半,放到中位数之后:
0 ~ 半数 取样数组、小于中位数、二分之一 ~ 半数 取样数组、枢轴、58%~3/4
取样数组、大于中位数、3/4~1 取样数组
你会意识枢轴前后又各自变回了起来规范,递归施行上述操作,便能对全数数组排序。
在意当取样数组用完的时候,直接变回普通的快排。

今世的抽样排序
此间的「今世」并不意味着更加好,只是让取样排序能更加好的适应四线程排序。
先是照旧是取样,取样的数额往往决意于线程的数额,比方说取了 p-1
个,就将数组分为 p 份。
对取样数组进行排序,得到 p 个区间(桶)。
遍历输入的数组,把成分扔到相应的桶里面。
把种种桶和对应的枢轴送到对应的线程进行排序。
汇总种种桶中的结果,排序达成。

测量检验结果:
图片 14
大约能提拔 5%~10% 的性能。

代码
using System;
using System.Diagnostics;

namespace Quick
{
    /// <summary>
    /// 取样排序类。
    /// </summary>
    public class SampleSort : QuickSort
    {
        /// <summary>
        /// 取样数组长度 2^k - 1 的阶数。
        /// </summary>
        public int K { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public SampleSort()
        {
            this.K = 8;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            if (a.Length < Math.Pow(2, this.K + 1))
            {
                // 小于 2^(k+1) 的数组直接进行快排
                base.Sort(a);
                return;
            }

            Shuffle(a);
            int samplehi = (int)Math.Pow(2, this.K) - 2;
            // 利用快速排序对取样数组进行排序
            base.Sort(a, 0, samplehi);
            // 找到取样数组的中位数
            int sampleMedian = samplehi / 2;
            // 将取样数组后半部分放到数组末尾
            int i = samplehi, j = a.Length - 1;
            while (i != sampleMedian)
                Exch(a, i--, j--);
            // 根据取样数组进行排序
            Sort(a, 0, sampleMedian, j, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="samplelo">取样数组的起始下标。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        /// <param name="samplehi">取样数组的终止下标。</param>
        private void Sort<T>(T[] a, int samplelo, int lo, int hi, int samplehi) where T : IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;

            int j = Partition(a, lo, hi);
            // 将前部的有序取样数组取半,后半部分放在枢轴前面。
            if (lo - samplelo > 1)
            {
                // p 应该始终指向有序部分的最后一项
                // v 应该始终指向有序部分的前面一项
                int p = lo - 1, v = j - 1;
                for (int i = 0; i < (lo - samplelo) / 2; i++)
                {
                    Exch(a, p--, v--);
                }
                Sort(a, samplelo, p, v, j - 1);
            }
            else
            {
                // 取样数组已经用完,退化为普通 Quicksort
                base.Sort(a, samplelo, j - 1);
            }

            // 将尾部有序取样数组取半,前半部分放在枢轴后面。
            if (samplehi - hi > 1)
            {
                // p 应该始终指向有序部分的前面一项
                // v 应该始终指向有序部分的最后一项
                int p = hi, v = j;
                for (int i = 0; i < (samplehi - hi) / 2; i++)
                {
                    Exch(a, ++p, ++v);
                }
                Sort(a, j + 1, v, p, samplehi);
            }
            else
            {
                // 取样数组已用完,退化为普通 Quicksort
                base.Sort(a, j + 1, samplehi);
            }
        }

        /// <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;
            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;
        }

        /// <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._24
{
    /*
     * 2.3.24
     * 
     * 取样排序。(W.Frazer,A.McKellar)
     * 实现一个快速排序,
     * 取样大小为 2^k-1。首先将取样得到的元素排序,
     * 然后在递归函数中使用样品的中位数切分。
     * 分为两部分的其余样品元素无需再次排序并可以分别应用于原数组的两个子数组。
     * 这种算法称为取样排序。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quickNormal = new QuickSort();
            SampleSort sampleSort = new SampleSort();
            int arraySize = 1600000;                        // 初始数组大小。
            const int kSteps = 10;                          // 取样 k 值的递增次数。
            const int trialTimes = 1;                       // 每次实验的重复次数。
            const int trialLevel = 2;                       // 双倍递增的次数。

            Console.WriteLine("ktnttsampletnormaltratio");
            for (int i = 0; i < kSteps; i++)
            {
                int array = arraySize;
                for (int j = 0; j < trialLevel; j++)
                {
                    double timeSample = 0;
                    double timeNormal = 0;
                    for (int k = 0; k < trialTimes; k++)
                    {
                        int[] a = SortCompare.GetRandomArrayInt(array);
                        int[] b = new int[a.Length];
                        a.CopyTo(b, 0);
                        timeNormal += SortCompare.Time(quickNormal, b);
                        timeSample += SortCompare.Time(sampleSort, a);

                    }
                    timeSample /= trialTimes;
                    timeNormal /= trialTimes;
                    if (arraySize < 10000000)
                        Console.WriteLine(sampleSort.K + "t" + array + "tt" + timeSample + "t" + timeNormal + "t" + timeSample / timeNormal);
                    else
                        Console.WriteLine(sampleSort.K + "t" + array + "t" + timeSample + "t" + timeNormal + "t" + timeSample / timeNormal);
                    array *= 2;
                }
                sampleSort.K++;
            }

        }
    }
}
另请参阅

至于取样排序的舆论(壹玖柒零 年):
Frazer W D, McKellar A C. Samplesort: A sampling approach to minimal
storage tree sorting[J]. Journal of the ACM (JACM), 1970, 17(3):
496-507.
维基百科中的取样排序:
Samplesort-Wikipedia
核心用到的类库链接:
Quick

2.3.25

题目

切换成插入排序。
达成八个高速排序,在子数组成分少于 M 时切换成插入排序。
用一点也不慢排序管理大小 N 分别为 10^3、10^4、10^5 和 10^6 的即兴数组,
传闻经验给出使其在你的情形中运维速度最快的 M 值。
将 M 从 0 变化到 30 的各类值所获得的平分运转时刻绘成曲线。
留心:你须要为算法 2.2 添加三个索要多少个参数的 sort() 方法以使
Insertion.sort(a, lo, hi) 将子数组 a[lo…hi] 排序。

解答

切换来插入排序的兑现相比较轻巧,在类内增加二个成员变量 M,在 Sort
方法里增添如下代码:

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);
}

上边放上实验结果:
N=1000
图片 15
N=10000
图片 16
N=100000
图片 17
N=1000000
图片 18

小于 8 的 M 值会比较方便。

代码

此地运用了 Background Worker 来防护程序失去响应,愈来愈多音信能够看
「另请参阅」部分。

using System;
using System.ComponentModel;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
using Quick;

namespace _2._3._25
{
    public partial class Form2 : Form
    {
        /// <summary>
        /// 测试数组大小。
        /// </summary>
        public int N = 100;

        public Form2(int n)
        {
            InitializeComponent();
            this.N = n;
        }

        /// <summary>
        /// 启动页面时启动后台测试。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void Form2_Shown(object sender, EventArgs e)
        {
            this.Text = "正在绘图";
            this.backgroundWorker1.RunWorkerAsync();
        }

        /// <summary>
        /// 后台测试方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e)
        {
            BackgroundWorker worker = sender as BackgroundWorker;
            QuickSortInsertion quickSortInsertion = new QuickSortInsertion();
            double[] timeRecord = new double[31];
            for (int i = 0; i <= 30; i++)
            {
                worker.ReportProgress(i * 3);
                quickSortInsertion.M = i;
                int[] data = SortCompare.GetRandomArrayInt(this.N);
                timeRecord[i] = SortCompare.Time(quickSortInsertion, data);
            }
            e.Result = timeRecord;
        }

        /// <summary>
        /// 更新后台进度方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_ProgressChanged(object sender, ProgressChangedEventArgs e)
        {
            this.Text = "正在绘图,已完成 " + e.ProgressPercentage + " %";
        }

        /// <summary>
        /// 测试完毕,进行绘图的方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
        {
            if (e.Error != null)
            {
                MessageBox.Show(e.Error.Message);
            }
            double[] result = e.Result as double[];

            Graphics graphics = this.CreateGraphics();

            // 获得绘图区矩形。
            RectangleF rect = this.ClientRectangle;
            float unitX = rect.Width / 10;
            float unitY = rect.Width / 10;

            // 添加 10% 边距作为文字区域。
            RectangleF center = new RectangleF
                (rect.X + unitX, rect.Y + unitY,
                rect.Width - 2 * unitX, rect.Height - 2 * unitY);

            // 绘制坐标系。
            graphics.DrawLine(Pens.Black, center.Left, center.Top, center.Left, center.Bottom);
            graphics.DrawLine(Pens.Black, center.Left, center.Bottom, center.Right, center.Bottom);
            graphics.DrawString(result.Max().ToString(), this.Font, Brushes.Black, rect.Location);
            graphics.DrawString(result.Length.ToString(), this.Font, Brushes.Black, center.Right, center.Bottom);
            graphics.DrawString("0", this.Font, Brushes.Black, rect.Left, center.Bottom);

            // 初始化点。
            PointF[] bluePoints = new PointF[result.Length];
            unitX = center.Width / result.Length;
            unitY = center.Height / (float)result.Max();

            for (int i = 0; i < result.Length; i++)
            {
                bluePoints[i] = new PointF(center.Left + unitX * (i + 1), center.Bottom - (float)(result[i] * unitY) - 10);
            }

            // 绘制点。
            for (int i = 0; i < result.Length; i++)
            {
                graphics.FillEllipse(Brushes.Blue, new RectangleF(bluePoints[i], new Size(10, 10)));
            }

            graphics.Dispose();

            this.Text = "绘图结果";
            int min = 0;
            for (int i = 0; i < result.Length; i++)
            {
                if (result[i] < result[min])
                    min = i;
            }
            string report = "M " + min + "rntime " + result[min];
            MessageBox.Show(report, "最优结果");
        }
    }
}

快捷排序类

using System;
using System.Diagnostics;
using Quick;

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

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

        /// <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>
        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;
            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;
        }

        /// <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;
            }
        }
    }
}
另请参阅

BackgroundWorker 组件 | Microsoft
Docs
Quick

2.3.26

题目

子数组的深浅。
编纂二个程序,在全速排序管理大小为 N 的数组的经过中,
当子数组的大小小于 M 时,排序方法要求切换为插入排序。
将子数组的轻重绘制作而成直方图。
用 N=10^5,M=10、20 和 50 测验你的主次。

解答

在切换为插入排序以前先记下一下当下子数组的深浅。
在排序类内加多贰个尺寸为 M+1 的数组,用于记录各类数组大小现身的次数。

结果如下(N=100000):
M=10
图片 19
M=20
图片 20
M=50
图片 21

代码
using System;
using System.ComponentModel;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
using Quick;

namespace _2._3._26
{
    public partial class Form2 : Form
    {
        private int M;
        private int N;

        public Form2(int m, int n)
        {
            InitializeComponent();
            this.M = m;
            this.N = n;
        }

        /// <summary>
        /// 启动页面时启动后台测试。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void Form2_Shown(object sender, EventArgs e)
        {
            this.Text = "正在绘图";
            this.backgroundWorker1.RunWorkerAsync();
        }

        /// <summary>
        /// 后台测试方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e)
        {
            BackgroundWorker worker = sender as BackgroundWorker;
            QuickSortInsertion quickSortInsertion = new QuickSortInsertion
            {
                M = this.M
            };
            int[] data = SortCompare.GetRandomArrayInt(this.N);
            worker.ReportProgress(50);
            quickSortInsertion.Sort(data);
            e.Result = quickSortInsertion.Counts;
        }

        /// <summary>
        /// 更新后台进度方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_ProgressChanged(object sender, ProgressChangedEventArgs e)
        {
            this.Text = "正在绘图,已完成 " + e.ProgressPercentage + " %";
        }

        /// <summary>
        /// 测试完毕,进行绘图的方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
        {
            if (e.Error != null)
            {
                MessageBox.Show(e.Error.Message);
            }
            //新建画布
            Graphics graphics = this.CreateGraphics();

            //翻转默认坐标系
            graphics.TranslateTransform(0, this.Height);
            graphics.ScaleTransform(1, -1);

            int[] countsOrigin = e.Result as int[];
            int[] counts = new int[countsOrigin.Length - 1];
            for (int i = 0; i < counts.Length; i++)
            {
                counts[i] = countsOrigin[i + 1];
            }

            //获取最大值
            double max = counts.Max();
            //计算间距
            double unit = this.Width / (3.0 * counts.Length + 1);
            double marginTop = 100;
            //计算直方图的矩形
            Rectangle[] rects = new Rectangle[counts.Length];
            rects[0].X = (int)unit;
            rects[0].Y = 0;
            rects[0].Width = (int)(2 * unit);
            rects[0].Height = (int)((counts[0] / max) * (this.Height - marginTop));
            for (int i = 1; i < counts.Length; ++i)
            {
                rects[i].X = (int)(rects[i - 1].X + 3 * unit);
                rects[i].Y = 0;
                rects[i].Width = (int)(2 * unit);
                rects[i].Height = (int)((counts[i] / (max + 1)) * (this.Height - marginTop));
            }

            //绘图
            graphics.FillRectangles(Brushes.Black, rects);

            //释放资源
            graphics.Dispose();

            this.Text = "绘图结果,最高次数:" + counts.Max() + " 最低次数:" + counts.Min();
        }
    }
}

急忙排序类

using System;
using System.Diagnostics;
using Quick;

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

        public int[] Counts;

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

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            this.Counts = new int[this.M + 1];
            for (int i = 0; i < this.M + 1; i++)
            {
                this.Counts[i] = 0;
            }
            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>
        protected void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;
            if (hi - lo <= this.M)
            {
                this.Counts[hi - lo]++;
                // 调用插入排序
                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;
            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;
        }

        /// <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;
            }
        }
    }
}
另请参阅

BackgroundWorker 组件 | Microsoft
Docs
Quick

2.3.27

题目

忽略小数组。
用试验相比较之下管理小数组的秘籍和练习 2.3.25 的拍卖措施的功能:
在便捷排序中一贯忽视小数组,仅在高效排序结束后运营贰遍插入排序。
在乎:能够透过这几个试验揣度出Computer的缓存大小,因为当数组大小超出缓存时这种办法的习性或者会下落。

解答

实行结果如下:
图片 22
P.S. 测验机上的缓存是 L1 128K,L2 512K,L3 4MB。

代码

QuickSortIgnore

using System;
using System.Diagnostics;
using Quick;

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

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

        /// <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);

            // 插入排序处理小数组
            for (int i = 0; i < a.Length; i++)
                for (int j = i; j > 0 && Less(a[j], a[j - 1]); j--)
                    Exch(a, j, j - 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)
            {
                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;
            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;
        }

        /// <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;
            }
        }
    }
}

QuickSortInsertion

using System;
using System.Diagnostics;
using Quick;

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

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

        /// <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>
        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;
            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;
        }

        /// <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._27
{
    /*
     * 2.3.27
     * 
     * 忽略小数组。
     * 用实验对比以下处理小数组的方法和练习 2.3.25 的处理方法的效果:
     * 在快速排序中直接忽略小数组,仅在快速排序结束后运行一次插入排序。
     * 注意:
     * 可以通过这些实验估计出电脑的缓存大小,
     * 因为当数组大小超出缓存时这种方法的性能可能会下降。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSortInsertion insertion = new QuickSortInsertion();
            QuickSortIgnore ignore = new QuickSortIgnore();
            int arraySize = 20000;                          // 初始数组大小。
            const int mSteps = 1;                           // M 值的递增次数。
            const int trialTimes = 4;                       // 每次实验的重复次数。
            const int trialLevel = 10;                      // 双倍递增的次数。

            Console.WriteLine("Mtnttignoretinserttratio");
            for (int i = 0; i < mSteps; i++)
            {
                int array = arraySize;
                for (int j = 0; j < trialLevel; j++)
                {
                    double timeIgnore = 0;
                    double timeInsertion = 0;
                    for (int k = 0; k < trialTimes; k++)
                    {
                        int[] a = SortCompare.GetRandomArrayInt(array);
                        int[] b = new int[a.Length];
                        a.CopyTo(b, 0);
                        timeInsertion += SortCompare.Time(insertion, b);
                        timeIgnore += SortCompare.Time(ignore, a);

                    }
                    timeIgnore /= trialTimes;
                    timeInsertion /= trialTimes;
                    if (arraySize < 10000000)
                        Console.WriteLine(ignore.M + "t" + array + "tt" + timeIgnore + "t" + timeInsertion + "t" + timeIgnore / timeInsertion);
                    else
                        Console.WriteLine(ignore.M + "t" + array + "t" + timeIgnore + "t" + timeInsertion + "t" + timeIgnore / timeInsertion);
                    array *= 2;
                }
                ignore.M++;
            }
        }
    }
}
另请参阅

Quick

2.3.28

题目

递归深度。
用经验性的切磋臆度切换阈值为 M 的飞跃排序在将大小为 N
的不重复数组排序时的平均递归深度,
其中 M=10、20 和 50,N=10^3、10^4、10^5 和 10^6。

解答

对 Sort 方法做修改,加多一个百多年不遇传递的 depth 参数,每加一层 depth
就加一,甘休时取左右非常的大的 depth 再次回到。

protected int Sort<T>(T[] a, int lo, int hi, int depth) where T: IComparable<T>
{
    if (hi <= lo)                   // 别越界
        return depth;
    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 depth;
    }
    int j = Partition(a, lo, hi);
    int left = Sort(a, lo, j - 1, depth + 1);
    int right = Sort(a, j + 1, hi, depth + 1);
    return Less(left, right) ? right : left;
}

测验结果
图片 23

代码
using System;
using System.Diagnostics;
using Quick;

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

        /// <summary>
        /// 上一次排序的最大递归深度。
        /// </summary>
        public int Depth { get; private set; }

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

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <returns>递归深度。</returns>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);
            this.Depth = Sort(a, 0, a.Length - 1, 0);
            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 int Sort<T>(T[] a, int lo, int hi, int depth) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return depth;
            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 depth;
            }
            int j = Partition(a, lo, hi);
            int left = Sort(a, lo, j - 1, depth + 1);
            int right = Sort(a, j + 1, hi, depth + 1);
            return Less(left, right) ? right : left;
        }

        /// <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;
            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;
        }

        /// <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.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _2._3._28
{
    /*
     * 2.3.28
     * 
     * 递归深度。
     * 用经验性的研究估计切换阈值为 M 的快速排序
     * 在将大小为 N 的不重复数组排序时的平均递归深度,
     * 其中 M=10、20 和 50,N=10^3、10^4、10^5 和 10^6。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("MtNtDepth");
            Trial(10);
            Trial(20);
            Trial(50);
        }

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

            // 由于排序前有 Shuffle,因此直接输入有序数组。
            // M=10
            sort.M = m;
            int totalDepth = 0;
            for (int N = 1000; N < 10000000; N *= 10)
            {
                for (int i = 0; i < trialTime; i++)
                {
                    int[] a = new int[N];
                    for (int j = 0; j < N; j++)
                    {
                        a[j] = j;
                    }
                    sort.Sort(a);
                    totalDepth += sort.Depth;
                }
                Console.WriteLine(sort.M + "t" + N + "t" + totalDepth / trialTime);
            }
        }
    }
}
另请参阅

Quick

2.3.29

题目

随机化。
用经验性的钻探比较随机挑选切分成分和正文所述的一发端就将数组随机化那三种政策的功效。
在子数组大小为 M 时举行切换,
将大小为 N 的不另行数组排序,当中 M=10、20 和 50,N=10^3、10^4、10^5 和
10^6。

解答

在快排类内部增多三个自便数产生器,每一回随机取枢轴并调换至第一人实行切分。

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;
}

测验结果:
图片 24

代码

选择随机枢轴的快排

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("MtNtshuffletrandomtshuffle/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

2.3.30

题目

Infiniti意况。
用起来随机化和非开端随机化的飞速排序测量检验演习 2.1.35 和演练 2.1.36
中描述的巨型非随机数组。
在将这个大数组排序时,乱序对高速排序的天性有什么影响?

解答

结果如下,在 N=六千000 时,随机采纳枢轴会比事先打乱快一点。
图片 25

代码
using System;
using Quick;

namespace _2._3._30
{
    /*
     * 2.3.30
     * 
     * 极端情况。
     * 用初始随机化和非初始随机化的快速排序测试练习 2.1.35 和练习 2.1.36 中描述的大型非随机数组。
     * 在将这些大数组排序时,乱序对快速排序的性能有何影响?
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSortInsertion insertionSort = new QuickSortInsertion();
            QuickSortRandomPivot randomSort = new QuickSortRandomPivot();
            int n = 5000000;

            // 高斯分布(正态分布)
            double[] arrayInsertion = SortCompare.GetNormalDistributionArray(n);
            double[] arraySelection = new double[n];

            arrayInsertion.CopyTo(arraySelection, 0);

            Console.WriteLine("Normal Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Random Pivot: " + SortCompare.Time(randomSort, arraySelection));
            Console.WriteLine();

            // 泊松分布
            arrayInsertion = SortCompare.GetPossionDistributionArray(n);
            arrayInsertion.CopyTo(arraySelection, 0);

            Console.WriteLine("Poission Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Random Pivot: " + SortCompare.Time(randomSort, arraySelection));
            Console.WriteLine();

            // 几何分布
            arrayInsertion = SortCompare.GetGeometricDistributionArray(n, 0.3);
            arrayInsertion.CopyTo(arraySelection, 0);

            Console.WriteLine("Geometric Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Random Pivot: " + SortCompare.Time(randomSort, arraySelection));
            Console.WriteLine();

            // 离散分布
            arrayInsertion = SortCompare.GetDiscretDistributionArray(n, new double[] { 0.1, 0.2, 0.3, 0.1, 0.1, 0.1, 0.1 });
            arrayInsertion.CopyTo(arraySelection, 0);

            Console.WriteLine("Discret Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Random Pivot: " + SortCompare.Time(randomSort, arraySelection));
            Console.WriteLine();

            // 一半是 0 一半是 1
            int[] arrayNormalInsertion = HalfZeroHalfOne(n);
            int[] arrayRandomPivot = new int[n];
            arrayNormalInsertion.CopyTo(arrayRandomPivot, 0);

            Console.WriteLine("half 0 and half 1");
            Console.WriteLine("Insertion:" + SortCompare.Time(insertionSort, arrayNormalInsertion));
            Console.WriteLine("Random Pivot:" + SortCompare.Time(randomSort, arrayRandomPivot));
            Console.WriteLine();

            // 一半是 0, 1/4 是 1, 1/8 是 2……
            arrayNormalInsertion = HalfAndHalf(n);
            arrayNormalInsertion.CopyTo(arrayRandomPivot, 0);

            Console.WriteLine("half and half and half ...");
            Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, arrayNormalInsertion));
            Console.WriteLine("Random Pivot:" + SortCompare.Time(randomSort, arrayRandomPivot));
            Console.WriteLine();

            // 一半是 0,一半是随机 int 值
            arrayNormalInsertion = HalfZeroHalfRandom(n);
            arrayNormalInsertion.CopyTo(arrayRandomPivot, 0);

            Console.WriteLine("half 0 half random");
            Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, arrayNormalInsertion));
            Console.WriteLine("Random Pivot:" + SortCompare.Time(randomSort, arrayRandomPivot));
        }

        /// <summary>
        /// 获取一半是 0 一半是 1 的随机 <see cref="int"/> 数组。
        /// </summary>
        /// <param name="n">数组大小。</param>
        /// <returns>一半是 0 一半是 1 的 <see cref="int"/>数组。</returns>
        static int[] HalfZeroHalfOne(int n)
        {
            int[] result = new int[n];
            Random random = new Random();
            for (int i = 0; i < n; i++)
            {
                if (random.NextDouble() >= 0.5)
                {
                    result[i] = 0;
                }
                else
                {
                    result[i] = 1;
                }
            }
            return result;
        }

        /// <summary>
        /// 生成 1/2 为 0, 1/4 为 1, 1/8 为 2 …… 的 <see cref="int"/> 数组。
        /// </summary>
        /// <param name="n">数组长度。</param>
        /// <returns>1/2 为 0, 1/4 为 1, 1/8 为 2 …… 的 <see cref="int"/> 数组。</returns>
        static int[] HalfAndHalf(int n)
        {
            int[] array = new int[n];
            HalfIt(0, 0, n / 2, array);
            Shuffle(array);
            return array;
        }

        /// <summary>
        /// 递归生成 1/2 为 0, 1/4 为 1, 1/8 为 2 …… 的 <see cref="int"/> 数组。
        /// </summary>
        /// <param name="start">填充起点。</param>
        /// <param name="number">起始编号。</param>
        /// <param name="length">填充长度</param>
        /// <param name="array">用于填充的数组。</param>
        /// <returns>一个 <see cref="int"/> 数组。</returns>
        static int[] HalfIt(int start, int number, int length, int[] array)
        {
            if (length == 0)
                return array;

            for (int i = 0; i < length; i++)
            {
                array[start + i] = number;
            }

            return HalfIt(start + length, number + 1, length / 2, array);
        }

        /// <summary>
        /// 生成一半是 0 一半是随机整数的 <see cref="int"/> 数组。
        /// </summary>
        /// <param name="n">数组大小。</param>
        /// <returns>生成一半是 0 一半是随机整数的 <see cref="int"/> 数组。</returns>
        static int[] HalfZeroHalfRandom(int n)
        {
            int[] array = new int[n];
            Random random = new Random();
            for (int i = 0; i < n / 2; i++)
            {
                array[i] = 0;
            }

            for (int i = n / 2; i < n; i++)
            {
                array[i] = random.Next();
            }

            Shuffle(array);

            return array;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <param name="a">需要打乱的数组。</param>
        static void Shuffle(int[] a)
        {
            int N = a.Length;
            Random random = new Random();
            for (int i = 0; i < N; i++)
            {
                int r = i + random.Next(N - i);// 等于StdRandom.uniform(N-i)
                int temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}
另请参阅

Quick

2.3.31

题目

运维时刻直方图。
编纂贰个主次,接受命令行参数 N 和 T,
用不慢排序对大小为 N 的随便浮点数数组进行 T 次排序,
并将具有运转时刻绘制作而成直方图。
令 N=10^3、10^4、10^5 和 10^6,
为了使曲线更平整,T 值越大越好。
本条练习最器重的地方在于找到适当的比例绘制出实验结果。

解答

以下有所结果 T=70
N=1000
图片 26
N=10000
图片 27
N=100000
图片 28
N=1000000
图片 29

代码
using System;
using System.ComponentModel;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
using Quick;

namespace _2._3._31
{
    public partial class Form2 : Form
    {
        private int N;
        private int T;

        public Form2(int n, int t)
        {
            InitializeComponent();
            this.N = n;
            this.T = t;
        }

        /// <summary>
        /// 启动页面时启动后台测试。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void Form2_Shown(object sender, EventArgs e)
        {
            this.Text = "正在绘图";
            this.backgroundWorker1.RunWorkerAsync();
        }

        /// <summary>
        /// 后台测试方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e)
        {
            BackgroundWorker worker = sender as BackgroundWorker;
            QuickSort quick = new QuickSort();

            double percentPerTrial = 100.0 / this.T;
            double[] totalTime = new double[this.T];
            for (int i = 0; i < this.T; i++)
            {
                double[] data = SortCompare.GetRandomArrayDouble(this.N);
                totalTime[i] = SortCompare.Time(quick, data);
                worker.ReportProgress((int)(percentPerTrial * i));
            }

            e.Result = totalTime;
        }

        /// <summary>
        /// 更新后台进度方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_ProgressChanged(object sender, ProgressChangedEventArgs e)
        {
            this.Text = "正在测试,已完成 " + e.ProgressPercentage + " %";
        }

        /// <summary>
        /// 测试完毕,进行绘图的方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
        {
            if (e.Error != null)
            {
                MessageBox.Show(e.Error.Message);
            }
            //新建画布
            Graphics graphics = this.CreateGraphics();

            //翻转默认坐标系
            graphics.TranslateTransform(0, this.Height);
            graphics.ScaleTransform(1, -1);

            double[] counts = e.Result as double[];

            //获取最大值
            double max = counts.Max();
            //计算间距
            double unit = this.Width / (3.0 * counts.Length + 1);
            double marginTop = 100;
            //计算直方图的矩形
            Rectangle[] rects = new Rectangle[counts.Length];
            rects[0].X = (int)unit;
            rects[0].Y = 0;
            rects[0].Width = (int)(2 * unit);
            rects[0].Height = (int)((counts[0] / max) * (this.Height - marginTop));
            for (int i = 1; i < counts.Length; ++i)
            {
                rects[i].X = (int)(rects[i - 1].X + 3 * unit);
                rects[i].Y = 0;
                rects[i].Width = (int)(2 * unit);
                rects[i].Height = (int)((counts[i] / (max + 1)) * (this.Height - marginTop));
            }

            //绘图
            graphics.FillRectangles(Brushes.Black, rects);

            //释放资源
            graphics.Dispose();

            this.Text = "绘图结果,最高耗时:" + counts.Max() + " 最低耗时:" + counts.Min();
        }
    }
}
另请参阅

BackgroundWorker 组件 | Microsoft
Docs
Quick

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*
*
Website