您的位置:澳门新葡8455最新网站 > 编程教学 > 遵照假诺核准的Filter方法

遵照假诺核准的Filter方法

发布时间:2019-12-13 19:07编辑:编程教学浏览(73)

    写在前头

    全副项目都托管在了 Github 上:
    探究更为有利的版本见:
    那风流倜傥节内容只怕会用到的库文件有 Quick,相似在 Github 上得以找到。
    善用 Ctrl + F 查找难点。

      转发请标记出处:

    习题&题解

      

    2.3.1

      Filter特征选拔格局是风流倜傥种启迪式方法,其核心绪维是:制订三个准绳,用来衡量每种特征/属性,对指标属性的主要性程度,以此来对具有特征/属性举办排序,或然进行优选操作。常用的衡量准绳有倘使核准的p值、相关周详、互消息、新闻增益等。本文基于候选属性和对象属性间关联性的借使核实,依赖p值的轻重量化各候选属性的首要程度。

    题目

    依据 Partition(卡塔尔(英语:State of Qatar) 方法的轨道的格式给出该办法是哪些切分数组 E A S Y Q U E S T I O N 的。

      设有$D $维数据集$mathfrak D = {vec x_n }_{n=1,...,N} $,其中$vec x_n = (x_{n1},...,x_{n,D-1},y_n) $,数据集$mathfrak D $由$D-1 $个候选属性$X_1,...,X_{D-1} $和1个对象属性$Y $刻画。属性在本文中分为三种档案的次序:一而再型属性和离散型属性,各属性均有望是三番三次型的依旧离散型的。本文的做事是经过对候选属性$X ; (in {X_1,...,X_{D-1} }卡塔尔(英语:State of Qatar)$和对象属性$Y $之间的关联性实行假诺考验,量化各候选属性单独预测目标属性的力量,依照属性类型的不一样,能够区分为4种情况:

    解答

    图片 1

      1)$X$和$Y $都以离散型属性;

    2.3.2

      2)$X$是连接型属性,$Y $是离散型属性;

    题目

    依据本节中赶快排序所示轨迹的格式给出连忙排序是怎么将数组 E A S Y Q U E S T I O N 排序的(出于演练的目标,能够忽视开首打乱数组的有个别)。

      3)$X$是离散型属性,$Y $是连连型属性;

    解答

    图片 2

      4)$X$和$Y $都以三番两回型属性。

    2.3.3

      对属性$X$和$Y $的关联性作即便核算的探究是:将$X$和$Y $看作是七个随机变量,将数据集$mathfrak D $中相关属性下的数值作为是随机变量的观测值,即有观测值$x_1,...,x_N $和$y_1,...,y_N $,依照这一个观测值布局出与$X$和$Y $独立性/关联性相关,且坚决守住已知布满(主即使$chi^2 $、$t $和$F $分布)的总结量,最终遵照已知遍布的可能率函数鲜明独立性查证的p值,用于属性$X$和$Y $关联程度的心气。

    题目

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

    1、基于Pearson $chi^2 $考验的离散变量关联性衡量

      针对属性$X$和$Y $都以离散型的,可以透过Pearson $chi^2 $考验方法核查$X$和$Y $的独立性。设$X$有$s $种大概取值,$Y $有$t $种大概取值,记$N_{ij} $为$X$取第$i $个值$Y$取第$j $个值的数码对象个数,且有$N_{icdot} = sum_{j=1}^t N_{ij} $,$N_{cdot j} = sum_{i=1}^s N_{ij} $,可作如下列联表:

    表 1:列联表

    图片 3

      假诺把$X$和$Y $看作是随机变量,则有概率布满,记为$p_{Xi} ; (i=1,...,s) $和$p_{Xj} ; (j=1,...,t卡塔尔国 $,且有二维随机变量$(X,Y卡塔尔 $的可能率布满:$p_{ij} ; (i=1,...,s; ; j= 1,...,t) $.易知,$forall i=1,...,s; ; j=1,...,t $有$p_{ij} = p_{Xi} cdot p_{Yj} $时,$X$与$Y $独立。由此有借使$$ begin{equation} H: ; p_{ij} = p_{Xi} cdot p_{Yj} quad (i=1,...,s; ; j=1,...,t) end{equation} $$旁观值接纳此就算的水平即为p值。 

      首先估量(1卡塔尔(英语:State of Qatar)式中的参数得$$ begin{equation} begin{split} hat p_{Xi} = N_{icdot}/N ; (i=1,...,s) \ hat p_{Yj} = N_{cdot j}/N ; (j=1,...,t) end{split} end{equation}$$进一步总结如下总计量:$$ begin{equation} begin{split} K & = sum_{i=1}^s sum_{j=1}^t frac{(N_{ij} - Nhat p_{Xi} hat p_{Yj})^2}{Nhat p_{Xi} hat p_{Yj}} \ & = N left ( sum_{i=1}^s sum_{j=1}^t frac{N_{ij}^2}{N_{i cdot}N_{cdot j}} - 1 right) end{split} end{equation} $$经认证计算量$K $的布满收敛于自由度为$ d = (s-1卡塔尔国(t-1卡塔尔(قطر‎ $的$chi^2 $布满,因而p值相仿为:$$ begin{equation} p_{value} = P(chi^2_d > K) end{equation} $$因为$chi^2_d $的可能率密度函数是已知的,所有轻巧通过(4卡塔尔(英语:State of Qatar)式总计出p值。

      由(3)式可知,当$K $越小时,$|N_{ij}/N - hat p_{Xi} hat p_{Yj}| rightarrow 0 $,由此反驳回绝(1卡塔尔式借使的概率越小,即$X$与$Y $独立的只怕性越大,由(4卡塔尔(英语:State of Qatar)式总括出的p值越大;相反地,p值越小,$X$与$Y $独立的或者性越小,相关联的恐怕性越大。因而p值越小,属性$X$越主要。

    图片 4

    图 1:Pearson $chi^2 $检验的p值

    解答

    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 次。

    2、基于单因子方差解析的一而再连续变量与离散变量间关联性衡量

      先来会见怎么着是单因子方差深入分析[[1]](file:///C:/Users/yua/Documents/%E5%85%B6%E5%AE%83/%E7%AC%94%E8%AE%B0/%E7%AC%94%E8%AE%B0%20-%20%E7%89%B9%E5%BE%81%E9%80%89%E6%8B%A9%E2%80%94%E2%80%94%E5%9F%BA%E4%BA%8E%E5%81%87%E8%AE%BE%E6%A3%80%E9%AA%8C%E7%9A%84Filter%E6%96%B9%E6%B3%95/Latex%E7%AC%94%E8%AE%B0%20-%20%E7%89%B9%E5%BE%81%E9%80%89%E6%8B%A9%E2%80%94%E2%80%94%E5%9F%BA%E4%BA%8E%E5%81%87%E8%AE%BE%E6%A3%80%E9%AA%8C%E7%9A%84Filter%E6%96%B9%E6%B3%95.docx#_edn1)

    另请参阅

    Number of largest element exchanges for quicksort-Stack Overflow

    2.1 单因子方差深入分析(one-way ANOVA)

      若是有$I $组试验,每组包蕴$J_i ; (i=1,...,I) $个样本,设$Y_{ij} $表示第$i $个试验组的第$j $个样板,$bar Y_i $表示第$i $组试验的样板均值,$bar Y $表示完全均值,有下式:$$ begin{equation} begin{split} sum_{i=1}^I sum_{j=1}^{J_i} (Y_{ij} - bar Y)^2 = & sum_{i=1}^I sum_{j=1}^{J_i} [(Y_{ij} - bar Y_i) + (bar Y_i - bar Y)]^2 \ = & sum_{i=1}^I sum_{j=1}^{J_i} (Y_{ij}

    • bar Y_i)^2 + sum_{i=1}^I sum_{j=1}^{J_i} (bar Y_i - bar Y)^2 \ & + 2sum_{i=1}^I sum_{j=1}^{J_i}(Y_{ij} - bar Y_i)(bar Y_i - bar Y) \ = & sum_{i=1}^I sum_{j=1}^{J_i} (Y_{ij} - bar Y_i)^2 + sum_{i=1}^I sum_{j=1}^{J_i} (bar Y_i - bar Y)^2 end{split} end{equation} $$上式简记为$SS_{TOT} = SS_W + SS_B $,即总的平方和优异组内平方和拉长组间平方和,$SS_W $代表试验组内部数据传布的胸襟,$SS_B $代表试验组之间传布的气量。

      设第$i $个试验组的期待为$mu_i $,可建议即便:$$ begin{equation} H: mu_1 = mu_2 = ... = mu_I end{equation} $$文献[1]中证实,当上述假诺创制,有$$ begin{equation} frac{E[SS_B]}{I-1} = frac{E[SS_W]}{J-I} end{equation} $$式中$E[cdot] $代表愿意,$J=sum_{i=1}^I J_i $.然则当(6卡塔尔(قطر‎式中倘诺不成立刻,有$$ begin{equation} frac{E[SS_B]}{I-1} > frac{E[SS_W]}{J-I} end{equation} $$

      又有证实,总计量$$ begin{equation} K = frac{SS_B/(I-1)}{SS_W/(J-I)} end{equation} $$在(6卡塔尔(英语:State of Qatar)式假若下信守自由度为$I-1 $和$J-I $的$F $分布,即$K sim F_{I-1, J-I} $.依据(7卡塔尔式和(8卡塔尔(英语:State of Qatar)式的剖析,当(6卡塔尔国式假诺为真时,$K $的值贴近于1,不然$K $的值应该非常大。因而能够根据$P(F_{I-1,J-I} > K)$选用或拒却假若$H $.

    2.3.4

    2.2 关联性衡量

      再来看看怎么着运用单因子方差解析衡量离散变量和一而再变量间的关联性。以$X$是离散变量,$Y $是一连变量为例($X$是延续变量,$Y $是离散变量的境况能够类推)。设$X$有$I $种只怕取值,记为$x_1, ..., x_I $,经过数据对象的顺序转换之后,总是能够得到如下表的多少格局:

    表 2:数据表

     

    $cdots $

    $X$

    $cdots $

    $Y $

    $vec x_1 $

    $cdots $

    $x_1 $

    $cdots $

    $y_{11} $

    $vdots $

    $vdots $

    $vdots $

    $vdots $

    $vdots $

    $vec x_{J_1} $

    $cdots $

    $x_1 $

    $cdots $

    $y_{1J_1} $

    $vdots $

    $vdots $

    $vdots $

    $vdots $

    $vdots $

    $vec x_{J_1 + ... + J_{i-1} + 1} $

    $cdots $

    $x_i $

    $cdots $

    $y_{i1} $

    $vdots $

    $vdots $

    $vdots $

    $vdots $

    $vdots $

    $vec x_{J_1 + ... + J_{i-1} + J_i} $

    $cdots $

    $x_i $

    $cdots $

    $y_{iJ_i} $

    $vdots $

    $vdots $

    $vdots $

    $vdots $

    $vdots $

    $vec x_{J_1 + ... + J_{I-1} + 1} $

    $cdots $

    $x_I $

    $cdots $

    $y_{I1} $

    $vdots $

    $vdots $

    $vdots $

    $vdots $

    $vdots $

    $vec x_{J_1 + ... + J_{I-1} + J_I} $

    $cdots $

    $x_I $

    $cdots $

    $y_{IJ_I} $

    其中$N = J_1 + ... + J_I $表示数据对象的总个数。也正是说数据对象足以像2.1小节那样依据$X$的取值划分为$I $组。

      根据概率论的文化,变量$X$与$Y $互相独立,则有$$ begin{equation} P(Y<y,X=x) = P(Y<y)P(X=x) end{equation} $$可是只要变量$X$与$Y$不独立,有$$ begin{equation} P(Y<y,X=x) = P(Y<y|X=x)P(X=x) end{equation} $$即当变量$X$与$Y $互相独立刻$P(Y<y|X=x卡塔尔(قطر‎ = P(Y<y卡塔尔国 $,因而在上述的各组中,变量$Y $具备雷同的遍及函数:$$ begin{equation} P(Y<y|X=x_1) = ... = P(Y<y|X=x_I) = P(Y<y) end{equation} $$假设$X$取值$x_i $的多少组下$Y sim N(mu_i, sigma^2卡塔尔(قطر‎ $,变量$X$与$Y $互相独马上一定有$mu_1 = ... = mu_I $,那与(6卡塔尔国式中的假使$H $完全相像,所以离散变量$X$与三番五次变量$Y $之间的关联性能够通过单因子方差分析衡量。

      首先依据(5卡塔尔式中的定义总计$SS_B $和$SS_W $,而后依照(9卡塔尔式总结出$K $值:$$ begin{equation} K = frac{sum_{i=1}^I J_i(bar y_i - bar y)^2 / (I-1)}{sum_{i=1}^I (J_i - 1) s^2_j / (N-I)} end{equation} $$其中$bar y_i = sum_{j=1}^{J_i} y_{ij} / J_i $,$bar y = sum_{i=1}^I J_i bar y_i / N $,$s^2_j = sum_{j=1}^{J_i} (y_{ij} - bar y_i)^2 / (J_i - 1卡塔尔 $,进而计算p值:$$ begin{equation} p_{value} = P(F_{I-1,J-I} > K) end{equation} $$

    依照上文的解析,当$X$与$Y $关联性越小,$K $越小,这时候p值越大;相反地,当$X $与$Y $关联性越大,$K $越大,p值越小。

    题目

    设若跳过起头打乱数组的操作,
    付给两个包罗 10 个成分的数组,
    使得 Quick.sort(卡塔尔 所需的相比次数高达最坏意况。

    3、基于Pearson相关周到字展现著性核算的一而再接二连三变量关联性度量

      针对均为接二连三变量的$X$和$Y $,依据数据集$mathfrak D $的取值,有数量对$(x_n, y_n) ; (n=1,...,N卡塔尔(قطر‎ $,设均值和方差的总结量如下:$$ bar x = frac 1N sum_{n=1}^N x_n $$$$bar y = frac 1N sum_{n=1}^N y_n$$$$ s^2_x = frac 1{N-1} sum_{n=1}^N (x_n - bar x)^2 $$$$s^2_y = frac 1{N-1} sum_{n=1}^N (y_n - bar y卡塔尔(قطر‎^2$$轻巧得到二维随机变量$(X,Y卡塔尔 $的Pearson相关周详的总结量:$$ begin{equation} r = frac{sum_{n=1}^N (x_n - bar x)(y_n - bar y)}{(N-1)sqrt{s^2_x s^2_y}} end{equation}$$注意(15卡塔尔(قطر‎式中$r $仅是经过样品获得的相关周密的总结量,如设变量$X$与$Y $的相关系数为$rho $,则$r $只是$rho $的推测。$X$是或不是与$Y $互相独立,$r=0 $说的不算,只有$rho =0 $才行,因而构造如下假诺:$$ begin{equation} H:rho = 0 end{equation} $$要求通过样板总计拿到的$r $的值,对(16卡塔尔(英语:State of Qatar)式的$H $做检查,如若选择$H $表示$X$与$Y $相互独立。

      为了对$H $做假若查证,首先对$r $作转换:$$ begin{equation} K = frac{rsqrt{N-2}}{sqrt{1-r^2}} end{equation} $$能够表明$K $遵守自由度为$N-2 $的t布满[[2]](file:///C:/Users/yua/Documents/%E5%85%B6%E5%AE%83/%E7%AC%94%E8%AE%B0/%E7%AC%94%E8%AE%B0%20-%20%E7%89%B9%E5%BE%81%E9%80%89%E6%8B%A9%E2%80%94%E2%80%94%E5%9F%BA%E4%BA%8E%E5%81%87%E8%AE%BE%E6%A3%80%E9%AA%8C%E7%9A%84Filter%E6%96%B9%E6%B3%95/Latex%E7%AC%94%E8%AE%B0%20-%20%E7%89%B9%E5%BE%81%E9%80%89%E6%8B%A9%E2%80%94%E2%80%94%E5%9F%BA%E4%BA%8E%E5%81%87%E8%AE%BE%E6%A3%80%E9%AA%8C%E7%9A%84Filter%E6%96%B9%E6%B3%95.docx#_edn2),即$K sim t_{N-2} $.评释过程很复杂,本文仅陈说注脚思路,假使查究,请参考文献[2]:假定随机变量$X$与$Y $是正态无相关的,总计相关周到总计量$r $的可能率密度函数$f(r卡塔尔(قطر‎$,依照(17卡塔尔国式的涉及总括出$K $的概率密度函数,发掘$K $的概率密度函数与自由度为$N-2 $的t布满的可能率密度函数完全大器晚成致,由此$K sim t_{N-2} $.

      基于$t_{N-2} $布满对$H $做假诺核算,可总括p值:$$ begin{equation} p_{value} = begin{cases} 0, & r^2 = 1 \ 2 cdot P(t_{N-2} > |K|), & text{otherwise} end{cases} end{equation} $$

    图片 5

    图 2:皮尔逊相关周密显然性核算的p值

      然则皮尔逊相关周到有一个欠缺:假如大肆变量$X$和$Y $之间存在线性关系,即$Y = aX+b $,则Pearson相关全面适用,但是即使$X$和$Y $之间的涉嫌是非线性的,则Pearson相关周详不适用。比方:

      例 1:设$X $与$Y $好似下的函数关系:$$ begin{equation} y = begin{cases} x, & 0 le x < 1 \ 3-x, & 1 le x le 2 end{cases} end{equation} $$此中$X $信守区间$[0,2] $的均匀分布,可算得$X $与$Y $相关周详为:$$ begin{equation} rho_{XY} = frac{E[(X-E(X))(Y-E(Y))]}{sqrt{E[(X-E(X))^2]E[(Y-E(Y))^2]}} = frac34 end{equation} $$然则豆蔻梢头旦有随机变量$Y' = X $,易得$rho_{XY'} = 1 $,有$rho_{XY} ne rho_{XY'} $.

      尝试分别对二维变量$(X,Y卡塔尔$和$(X,Y'卡塔尔国 $作如图所示的离散化:$X$、$Y $、$Y’ $等宽的剪切成4个小区间,依次以1、2、3、4登入。

    图片 6

    图 3:离散化

      离散化后,图中土黑方格代表概率为零,紫色方格代表可能率为$四分三$,如$P(X=1,Y=1卡塔尔=52% $.依照$chi^2 $核查的规律,易知离散化后,$(X,Y卡塔尔$与$(X,Y'卡塔尔 $有相符的关联性,与上述Pearson相关全面的结果并不符合。

      雷同例 1的事例还大概有不菲,那几个都以由于Pearson不扶植非线性相关性引起的,在应用上述办法做特色选用时,供给小心那点。

    解答

    每一遍只让枢轴变为已排序,那正是最坏景况。
    这种时候枢轴是当前子数组的最大值 / 最小值。
    由于在大家的兑现中延续取子数组的第三个成分作为枢轴。
    因此二个已排序的数组能够达到最坏情况,相比次数到达 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
    

    仿效文献


    [1] Rice, J.A.著, 田金方译. 数理总结与数据拆解深入分析(原书第3版卡塔尔[M]. 机械工业出版社, 二零一二, pp. 328-333.

    [2] Fisz M. 可能率论及数理总括[M]. 北京科学能力出版社, 一九六一.

    另请参阅

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

    2.3.5

    题目

    交付后生可畏段代码将已知独有三种主键值的数组排序。

    解答

    法定达成:

    算法 gif 动图
    图片 7

    代码
    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 $ 的反差。

    解答

    运维结果如下:
    图片 8

    代码

    新建叁个 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卡塔尔(英语:State of Qatar) $ 都满意下式:
    [ 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卡塔尔(英语:State of Qatar) $ ,大家有始发标准 $ 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 ]
    试验结果:
    图片 9

    代码

    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(卡塔尔(英语:State of Qatar) 在拍卖 N 个总体重新的因素时大概要求多少次相比较?

    解答

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

    2.3.9

    题目

    请表明 Quick.sort()在拍卖唯有三种主键值时的行事,以至在拍卖唯有二种主键值的数组时的表现。

    解答

    切分时,枢轴左边都以低于(或等于)枢轴的,
    侧面都以凌驾(或等于)枢轴的
    唯有二种主键值时,
    首先次切分之后,某旁边的成分将全部相似
    (假设枢轴选了超大的,那么右边将总体等同,反之则左侧全体同等)

    唯有三种主键值时,和平时急速排序并无两样。
    但假设第一次切分时精选了中间值作为枢轴,且中间值唯有三个
    那正是说只须求叁遍切分数组便会静止。

    2.3.10

    题目

    Chebyshev 不等式申明,三个随机变量的正规化差别离均值大于 k 的概率小于 1/k^2 。
    对此 N=100 万,用 Chebyshev 不等式计算火速排序所使用的可比次数抢先 1000 亿次的概率(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 的。

    解答

    图片 10

    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-London高校
    《算法导论》中有关自由 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卡塔尔(英语:State of Qatar) $。
    [ 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 - Carnegie梅隆大学
    假定照旧无法知晓为啥反复切分不影响概率,能够参见三门题材的表明:
    蒙提霍尔难点 - 维基百科
    蒙提霍尔难点(又称三门主题素材、山羊小车难题)的正解是怎么样?- 果壳网

    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 的数组做特殊管理,通过二遍相比直接排序并重临。

    测验结果:
    图片 11

    代码

    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 放到数组的尾声作为哨兵,去掉左侧界的论断。
    再者让左右两边指针都向中档移动两位,减少不须要的比较。

    测验结果,相比较普通快排质量升官约 十一分之意气风发,和三取样快排分裂相当小。
    图片 12

    代码

    五取样快排

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

    是因为栈操作比函数调用操作消耗费时间间越来越长,因而测验后的结果会比原本快排慢 肆分之三左右。
    图片 13

    代码

    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 所示。
    请注意:
    此间达成的代码和正文中付出的代码时等价的,
    因为此地额外的交流用于和切分成分相等的要素,
    而本文中的代码将卓越的交流用于和切分成分不等的要素。

    解答

    法定完毕见:

    急速三向切分

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

    Ninther 算法

    合法完毕中用到了 Ninther 算法用于选取雷同中位数(作为枢轴),
    该算法由 John Tukey 在 1979 年建议,散文援引见「另请参阅」部分。
    那个算法的合计实际不会细小略,如果大家有多个数 $ 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 $ 正是中位数。

    赢得多个数中的中位数

    实在,大家能够平昔画出多个数排列的持有比较大希望,得到决策树。
    图片 15
    接下来依照决策树写出取中位数的算法:

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

    测量检验结果

    增进度约 百分之三十三 左右的品质。
    图片 16

    代码

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

    至于这种高速排序算法的根源以致八个数的中位数的选项算法,请参阅下边这篇 壹玖玖壹 年的故事集:
    Bentley J L, McIlroy M D. Engineering a sort function[J]. Software: Practice and Experience, 1993, 23(11): 1249-1265.
    上边那份 二零零一 年的 PPT 详细表明和深入分析了合法实今世码的思路和性情:
    Sedgewick R, Bentley J. Quicksort is optimal[J]. Knuthfest, Stanford University, Stanford, 2002.
    关于采用中位数 Ninther 算法,请参阅下边那篇 一九七七 年的舆论:
    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)操作将取样数组和剩余数组归总。
    其次种方式
    抽样数组和剩余数组保存在同样片空间里,那也是那份题解所完毕的措施。
    图片 17
    在打乱输入数组之后,取前 2^k-1 个因素作为取样数组,用快排对其排序。
    下一场把取样数组的后半片段放到任何数组的尾声。
    如此那般操作的结果是输入数组分为了多少个部分:
    长期以来的取样数组、取样数组的中位数、冬季的剩余数组、有序的抽样数组。
    中位数则位居第风度翩翩有些的终极,大家将其用作枢轴对剩余数组进行切分,数组变为:
    不改变的抽样数组、小于中位数的有的、枢轴、大于中位数的局地、有序的取样数组
    接下去我们再对首个部分取半,放到中位数以前;对最终风姿浪漫某个取半,放到中位数之后:
    0 ~ 1/4 取样数组、小于中位数、一半 ~ 47% 取样数组、枢轴、八分之大器晚成~3/4 取样数组、大于中位数、3/4~1 取样数组
    您会意识枢轴前后又分别变回了起头标准,递归实施上述操作,便能对全体数组排序。
    留意当取样数组用完的时候,直接变回普通的快排。

    今世的取样排序
    此处的「今世」并不意味更好,只是让取样排序能更加好的适应八线程排序。
    首先仍然是取样,取样的数目往往决定于线程的数码,比如说取了 p-1 个,就将数组分为 p 份。
    对取样数组举行排序,获得 p 个区间(桶)。
    遍历输入的数组,把成分扔到相应的桶里面。
    把各样桶和呼应的枢轴送到对应的线程实行排序。
    聚集各样桶中的结果,排序完成。

    测试结果:
    图片 18
    大要能进步 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++;
                }
    
            }
        }
    }
    
    另请参阅

    关于取样排序的舆论(1966 年):
    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
    图片 19
    N=10000
    图片 20
    N=100000
    图片 21
    N=1000000
    图片 22

    稍低于 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
    图片 23
    M=20
    图片 24
    M=50
    图片 25

    代码
    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 的拍卖措施的法力:
    在高速排序中一向忽略小数组,仅在飞快排序甘休后运转三遍插入排序。
    静心:能够透过这个实验推断出计算机的缓存大小,因为当数组大小超过缓存时这种方法的习性或然会降低。

    解答

    推行结果如下:
    图片 26
    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;
    }
    

    测验结果
    图片 27

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

    测验结果:
    图片 28

    代码

    选用随机枢轴的快排

    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

    题目

    十二万分景况。
    用起来随机化和非早先随机化的高效排序测验演习 2.1.35 和演练 2.1.36 中陈述的大型非随机数组。
    在将这几个大数组排序时,乱序对便捷排序的品质有何影响?

    解答

    结果如下,在 N=5000000 时,随机筛选枢轴会比事情未发生前打乱快一点。
    图片 29

    代码
    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
    图片 30
    N=10000
    图片 31
    N=100000
    图片 32
    N=1000000
    图片 33

    代码
    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 库

    本文由澳门新葡8455最新网站发布于编程教学,转载请注明出处:遵照假诺核准的Filter方法

    关键词:

上一篇:自动属性加强,反射赋值的连锁

下一篇:没有了