soaye,壕莪,8月14日是什么情人节
整个项目都托管在了 Github 上：
查找更为方便的版本见：
这一节内容可能会用到的库文件有 Quick，同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。
按照 Partition() 方法的轨迹的格式给出该方法是如何切分数组 E A S Y Q U E S T I O N 的。
按照本节中快速排序所示轨迹的格式给出快速排序是如何将数组 E A S Y Q U E S T I O N 排序的（出于练习的目的，可以忽略开头打乱数组的部分）。
对于长度为 N 的数组，在 Quick.sort() 执行时，其最大元素最多会被交换多少次？
N / 2
在快速排序中，一个元素要被交换，有以下两种情况
1.该元素是枢轴，在切分的最后一步被交换
2.该元素位于枢轴错误的一侧，需要被交换到另一侧去
注意，以上两种情况在一次切分中只会出现一次
首先来看第一种情况，如果一个元素变成了枢轴
那么在之后的切分中该元素会被排除，不存在后续的交换。
因此我们的目标应该是：
最大的元素总是出现在错误的一侧，同时切分的次数尽可能多。
接下来我们来思考如何构造这样的数组
由于我们针对的是最大的元素，因此「错误的一侧」就是枢轴的左侧。
为了使切分的次数尽可能多，我们需要保持最大值移动的距离尽量短。
但如果每次只移动一位的话，下一次切分时最大值就会变成枢轴
例如 4 10 3 5 6，枢轴为 4，交换后数组变为：
4 3 10 5 6
随后 4 和 3 交换
3 4 10 5 6
下一次切分时 10 会变成枢轴，不再参与后续的切分。
因此我们需要让最大值每次移动两个元素。
考虑下面的数组：
2 10 4 1 6 3 8 5 7 9
第一次切分的时候，枢轴为 2，10 和 1 进行交换
数组变为：
2 1 4 10 6 3 8 5 7 9
随后枢轴交换，数组变为：
1 2 4 10 6 3 8 5 7 9
第二次切分，枢轴为 4，10 和 3 进行交换。
1 2 4 3 6 10 8 5 7 9
随后枢轴交换 数组变为：
1 2 3 4 6 10 8 5 7 9
第三次切分，枢轴为 6，10 和 5 交换
1 2 3 4 6 5 8 10 7 9
随后枢轴交换，数组变为：
1 2 3 4 5 6 8 10 7 9
第四次切分，枢轴为 8，10 和 7 交换
1 2 3 4 5 6 8 7 10 9
枢轴交换，数组变为
1 2 3 4 5 6 7 8 10 9
最后一次切分，枢轴为 10，直接交换
1 2 3 4 5 6 7 8 9 10
我们可以总结出要构造这样的数组的模板
a2 max a3 a1
其中 a1 < a2 < a3 < max
max 每轮切分移动两格，总共切分 N/ 2 次。
假如跳过开头打乱数组的操作，
给出六个含有 10 个元素的数组，
使得 Quick.sort() 所需的比较次数达到最坏情况。
每次只让枢轴变为已排序，这就是最坏情况。
这种时候枢轴是当前子数组的最大值 / 最小值。
由于在我们的实现中总是取子数组的第一个元素作为枢轴。
因此一个已排序的数组可以达到最坏情况，比较次数达到 O(n^ 2)。
如果换作取最后一个元素，最坏情况会变成逆序数组。
我们的实现中如果碰到与枢轴相等的元素也会停止循环，
因此如果数组中有重复的元素会减少比较次数。
例如：
1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 11 3 4 5 6 7 8 9 10 11 12 4 5 6 7 8 9 10 11 12 13 5 6 7 8 9 10 11 12 13 14 6 7 8 9 10 11 12 13 14 15
给出一段代码将已知只有两种主键值的数组排序。
官方实现：
算法 gif 动图
我要评论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++;
}
}
}
}
编写一段代码来计算 $ C_N $ 的准确值，
在 $ N=100、1000 $ 和 $10 000 $ 的情况下比较准确值和估计值 $ 2NlnN $ 的差距。
运行结果如下：
新建一个 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("\tlo\tj\thi");
}
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("N\t准确值\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;
}
}
}
}
在使用快速排序将 N 个不重复的元素排序时，
计算大小为 0、1 和 2 的子数组的数量。如果你喜欢数学，请推导；
如果你不喜欢，请做一些实验并提出猜想。
我讨厌数学= =
证明：
我们设 $ C_0(n) $ 代表将 $ n $ 个不重复元素排序时大小为 0 的数组的数量。
同理有 $ C_1(n) $ 和 $ C_2(n) $ 代表大小为 1 的数组的数量以及大小为 2 的数组的数量。
设 k 代表切分位置，显然切分位置随机且概率相等，在 1~n 之间均匀分布。
根据条件，$ C_0(n), C_1(n),C_2(n) $ 都满足下式：
\[
C(n)= \frac{\sum_{k=1}^{n}(C(k-1)+C(n-k))}{n}
\]
根据快速排序算法， $ \sum_{k=1}^{n}C(k-1)=\sum_{k=1}^{n}C(n-k) $ ，因此
\[
C(n)=\frac{2\sum_{k=1}^{n}C(k-1)}{n}\\
nC(n)=2\sum_{k-1}^{n}C(k-1)
\]
同理代入 $ n-1 $ 有
\[
(n-1)C(n-1)=2\sum_{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)}\times\frac{C(n-1)}{C(n-2)}\times\dots\times\frac{C(m+1)}{C(m)}=
\frac{n+1}{n}\times\frac{n}{n-1}\times\dots\times\frac{m+2}{m+1}\\
\frac{C(n)}{C(m)}=\frac{n+1}{m+1}\\
C(n)=C(m)\frac{n+1}{m+1}，n>m
\]
对于 $ C_0(n) $ ，我们有初始条件 $ C_0(0)=1, C_0(1)=0,C_0(2)=C_0(0)+C_0(1)=1 $
\[
C_0(n)=\frac{n+1}{3}, n>2
\]
对于 $ C_1(n) $ ，我们有初始条件 $ C_1(0)=0,C_1(1)=1,C_1(2)=C_1(0)+C_1(1)=1 $
\[
C_1(n)=\frac{n+1}{3},n>2
\]
对于 $ C_2(n) $ ，我们有初始条件 $ C_2(0)=C_2(1)=0,C_2(2)=1,C_2(3)=\frac{2\times(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
\]
实验结果：
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("\tlo\tj\thi");
}
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("n\t0\t1\t2");
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.sort() 在处理 N 个全部重复的元素时大约需要多少次比较？
每次切分都会把数组平分，共切分 logN 次（二分法），每次切分比较 N 次（i 和 j 会一位一位地从两边向中间靠拢）。
共比较 NlogN 次。
请说明 Quick.sort() 在处理只有两种主键值时的行为，以及在处理只有三种主键值的数组时的行为。
切分时，枢轴左侧都是小于（或等于）枢轴的，
右侧都是大于（或等于）枢轴的
只有两种主键值时，
第一次切分之后，某一侧的元素将全部相同
（如果枢轴选了较大的，那么右侧将全部相同，反之则左侧全部相同）
只有三种主键值时，和一般快速排序并无不同。
但如果第一次切分时选择了中间值作为枢轴，且中间值只有一个
那么只需要一次切分数组便会有序。
Chebyshev 不等式表明，一个随机变量的标准差距离均值大于 k 的概率小于 1/k^2 。
对于 N=100 万，用 Chebyshev 不等式计算快速排序所使用的比较次数大于 1000 亿次的概率（0.1N^2）。
切比雪夫不等式（Chebyshev’s inequality）
\[
P(|X-\mu|\geq k\sigma)\leq \frac{1}{k^2}
\]
其中，$ \mu $ 代表期望，$ \sigma $ 代表标准差。
对于快速排序的比较次数来说，$ \mu = 2N\ln 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
\]
假如在遇到和切分元素重复的元素时我们继续扫描数组而不是停下来，
证明使用这种方法的快速排序在处理只有若干种元素值的数组时运行时间是平方级别的。
只有若干种元素值意味着大量的连续重复。
（由于存在打乱这一步骤，不存在连续重复的可能性是很低的）
接下来我们考虑这样的连续重复在修改后的快排下的性能。
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 $
因此对于值相同的子数组，这样的快排运行时间是平方级别的
那么当数组中这样的连续重复内容越多，运行时间就越接近平方级别。
按照代码所示轨迹的格式给出信息量最佳的快速排序第一次是如何切分
数组 B A B A B A B A C A D A B R A 的。
在最佳、平均和最坏情况下，快速排序的递归深度分别是多少？
这决定了系统为了追踪递归调用所需的栈的大小。
在最坏情况下保证递归深度为数组大小的对数级的方法请见练习 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=2\times\max(Y_{i-1},Y_{n-i})
\]
我们把 $ Y_n $ 代入，可得：
\[
\begin{align*}
E(Y_n)
&=\sum_{i=1}^{n}\frac{1}{n}E\lbrack2\times\max(Y_{i-1}, Y_{n-i})\rbrack\\
&=\frac{2}{n}\sum_{i=1}^{n}E\lbrack\max(Y_{i-1},Y_{n-i})\rbrack\\
\end{align*}
\]
接下来我们去掉最大值运算，根据最大值的性质，下式显然成立：
\[
E\lbrack\max(X,Y)\rbrack\le E\lbrack\max(X,Y)+\min(X,Y)\rbrack=E\lbrack X+Y\rbrack=E\lbrack X\rbrack+E\lbrack Y\rbrack
\]
代入可得：
\[
E(Y_n)
\le\frac{2}{n}\sum_{i=1}^{n}(E\lbrack Y_{i-1}\rbrack + E\lbrack Y_{n-i} \rbrack)
=\frac{2}{n}\sum_{i=0}^{n-1}2E\lbrack Y_i\rbrack
=\frac{4}{n}\sum_{i=0}^{n-1}E\lbrack Y_i\rbrack
\]
大小为 0 的数组构成的 BST 的高度显然为 0，我们设 $ Y_0=0 $ 。接下来用一个组合数公式来构造上界：
\[
\begin{align*}
0&=Y_0=E\lbrack Y_0 \rbrack\le \frac{1}{4}\begin{pmatrix}3\\3\end{pmatrix}=\frac{1}{4}\\
1&=Y_1=E\lbrack Y_1 \rbrack\le\frac {1}{4}\begin{pmatrix}3+1\\3\end{pmatrix}=1 \\
\vdots \\
Y_i &=E\lbrack Y_i\rbrack\le\frac{1}{4}\begin{pmatrix}i+3\\3\end{pmatrix}
\end{align*}
\]
注意这里的组合数公式为：
\[
\begin{pmatrix}n\\r\end{pmatrix}=\frac{r!}{r!(n-r)!}
\]
代入可得：
\[
\begin{align*}
E(Y_n) &\le \frac{4}{n}\sum_{i=0}^{n-1}E\lbrack Y_i\rbrack \\
&\le\frac{4}{n}\sum_{i=0}^{n-1}\frac{1}{4}\begin{pmatrix}i+3\\3\end{pmatrix} \\
&=\frac{1}{n}\sum_{i=0}^{n-1}\begin{pmatrix}i+3\\3\end{pmatrix}
\end{align*}
\]
接下来我们去掉求和符号，首先根据组合数的性质，有以下等式成立
\[
\begin{align*}
\begin{pmatrix}n\\k\end{pmatrix}&=\begin{pmatrix}n-1\\k-1\end{pmatrix}+\begin{pmatrix}n-1\\k\end{pmatrix} \\
\begin{pmatrix}n\\n\end{pmatrix}&=1
\end{align*}
\]
我们把求和式展开得到：
\[
\begin{align*}
\sum_{i=0}^{n-1}\begin{pmatrix}i+3\\3\end{pmatrix}
&=\begin{pmatrix}3\\3\end{pmatrix} + \begin{pmatrix}4\\3\end{pmatrix}+\cdots+\begin{pmatrix}n+2\\3\end{pmatrix} \\
&=\begin{pmatrix}4\\4\end{pmatrix} + \begin{pmatrix}4\\3\end{pmatrix}+\cdots+\begin{pmatrix}n+2\\3\end{pmatrix} \\
&=\begin{pmatrix}n+3\\4\end{pmatrix}
\end{align*}
\]
代入可得：
\[
\begin{align*}
E(Y_n) &\le\frac{1}{n}\sum_{i=0}^{n-1}\begin{pmatrix}i+3\\3\end{pmatrix}\\
&=\frac{1}{n}\begin{pmatrix}n+3\\4 \end{pmatrix} \\
&=\frac{1}{n}\cdot\frac{(n+3)!}{4!(n-1)!} \\
&=\frac{1}{4}\cdot\frac{(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}\) ，因此 \(E\lbrack Y_n \rbrack=E\lbrack 2^{h_n} \rbrack\)。
由于 \(f(x)=2^x\) 是个凸函数，可以应用延森不等式（凸函数的割线一定在函数上方），即 \(2^{E\lbrack h_n\rbrack}\le E\lbrack Y_n\rbrack\)。
于是得到结论：
\[
2^{E\lbrack h_n\rbrack} \le \frac{n^3+6n^2+11n+6}{24} \\
E\lbrack h_n \rbrack\le \log(\frac{n^3+6n^2+11n+6}{24})
\]
快速排序的递归树可以视为 BST 的结论可以在下面这个 PPT 的第 5 页找到。
《算法导论》中关于随机 BST 高度的证明（P321 Theorem12.4）
也可以参考下面这个链接获得更详细的解释。
证明在用快速排序处理大小为 N 的不重复数组时，
比较第 i 大和第 j 大元素的概率为 2/(j - i + 1)，并用该结论证明命题 K。
中文版题目有误，详见官方勘误页面：
假设 $ i < j $ 。
首先，在快速排序中，如果两个元素要发生交换，意味着其中一个元素被选为枢轴。
而且数组中的元素各不相同，那么两个特定的元素的比较最多发生一次。
那么先考虑一个特殊情况，$ i = 1, j = n $ ，即求最大值和最小值比较的概率。
此时，一旦枢轴不是这两个元素之一，
最大值和最小值会被分到两个不同的子数组，无法发生比较。
因此在这种特例下第 $ i $ 大的元素和第 $ j $ 大的元素发生比较的概率为 $ \frac{2}{n} = \frac{2}{j-i+1} $ 。
接下来考虑一般情况，如果枢轴选择了第 $ i $ 到第 $ j $ 大之外的元素，
那么第 $ i $ 大和第 $ j $ 大的元素会被分到同一个子数组里，重复上述过程。
因此我们所求的概率只和从第 $ i $ 大到第 $ j $ 大之间的元素有关，概率为 \(\frac{2}{j-i+1}\)。
（举个例子，一个箱子里有 2 个红球、1个蓝球和 7 个白球，现在摸球而不放回。
如果摸到白球可以再摸一次，直到摸到红球或蓝球为止。
显然在这样的规则下摸到红球或蓝球的概率为 1，即白球对概率没有影响。）
现在我们已经得到了某两个元素比较的概率 \(E(X_{ij})\)，接下来我们求每两个元素比较的概率 $ E(X) $。
\[
\begin{align*}
E(X)
&= \sum_{i=1}^{n}\sum_{j=i+1}^{n}E(X_{ij})\\
&=\sum_{i=1}^{n}2(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n-i+1}) \\
&=2n(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n-i+1})
\end{align*}
\]
根据调和级数的性质（$ \ln (n) < 1+ \frac{1}{2}+ \cdots + \frac{1}{n} < 1+\ln(n) $），可以得到结论：
\[
E(X) \le 2n \ln(n)
\]
下面这个链接里的 3.4.2 节给出了解法。
如果还是不能理解为什么多次切分不影响概率，可以参考三门问题的解释：
螺丝和螺帽。（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;
}
}
}
下面这个网站给出了这道题的解法，还给出了另一种确定性算法（非随机的算法）的论文链接。
最佳情况。
编写一段程序来生成使算法 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();
}
}
}
哨兵。
修改算法 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("QSort\tQSort with Sentinels\t");
Console.WriteLine(time1 + "\t" + time2 + "\t");
}
}
}
三取样切分。
为快速排序实现正文所述的三取样切分（参见 2.3.3.2 节）。运行双倍测试来确认这项改动的效果。
每次切分时都取前三个元素的中位数作为枢轴，这可以带来约 5%~10% 的性能提升。
这里通过三次比较将前三个数排序，然后把三个数中的中位数放到数组开头，最大值放到数组末尾。
最大值被放到了末尾，枢轴不可能大于末尾的这个数，因此右边界判断可以去掉。
同时由于枢轴不可能小于自身，因此左边界判断也可以去掉。
这样就可以把切分中的两个边界判断全部去掉了。
最后对于大小为 2 的数组做特殊处理，通过一次比较直接排序并返回。
测试结果：
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("n\tmedian\tnormal\tratio");
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;
}
}
}
}
五取样切分。
实现一种基于随机抽取子数组中 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 放到数组的最后作为哨兵，去掉右边界的判断。
同时让左右两侧指针都向中间移动两位，减少不必要的比较。
测试结果，对比普通快排性能提升约 10%，和三取样快排区别不大。
五取样快排
using System;
using System.Diagnostics;
using Quick;
namespace _2._3._19
{
/// <summary>
/// 五取样快速排序
/// </summary>
public class QuickSortMedian5 : BaseSort
{
/// <summary>
/// 默认构造函数。
/// </summary>
public QuickSortMedian5() {}
/// <summary>
/// 用快速排序对数组 a 进行升序排序。
/// </summary>
/// <typeparam name="T">需要排序的类型。</typeparam>
/// <param name="a">需要排序的数组。</param>
public override void Sort<T>(T[] a)
{
Shuffle(a);
Sort(a, 0, a.Length - 1);
Debug.Assert(IsSorted(a));
}
/// <summary>
/// 用快速排序对数组 a 的 lo ~ hi 范围排序。
/// </summary>
/// <typeparam name="T">需要排序的数组类型。</typeparam>
/// <param name="a">需要排序的数组。</param>
/// <param name="lo">排序范围的起始下标。</param>
/// <param name="hi">排序范围的结束下标。</param>
private void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
{
if (hi <= lo) // 别越界
return;
// 少于五个元素的数组直接进行插入排序
if (hi - lo + 1 < 5)
{
int n = hi - lo + 1;
for (int i = lo; i - lo < n; i++)
{
for (int k = i; k > 0 && Less(a[k], a[k - 1]); --k)
{
Exch(a, k, k - 1);
}
}
return;
}
int j = Partition(a, lo, hi);
Sort(a, lo, j - 1);
Sort(a, j + 1, hi);
}
/// <summary>
/// 对数组进行切分，返回枢轴位置。
/// </summary>
/// <typeparam name="T">需要切分的数组类型。</typeparam>
/// <param name="a">需要切分的数组。</param>
/// <param name="lo">切分的起始点。</param>
/// <param name="hi">切分的末尾点。</param>
/// <returns>枢轴下标。</returns>
private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
{
int i = lo, j = hi + 1;
// 假设为 a b c d e 五个数字
// 首先对 b c 排序
if (Less(a[lo + 2], a[lo + 1]))
Exch(a, lo + 2, lo + 1);
// 然后再排序 d e
if (Less(a[lo + 4], a[lo + 3]))
Exch(a, lo + 4, lo + 3);
// 这时满足 b < c, d < e
// 比较 b d，把较小的一组放到 b c 的位置上去
if (Less(a[lo + 3], a[lo + 1]))
{
Exch(a, lo + 1, lo + 3);
Exch(a, lo + 2, lo + 4);
}
// 这时满足 b < c, b < d < e，即 b
-
您可能感兴趣的文章:
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！
点击进行留言回复
Blazor server side 自家的一些开源的, 实用型项目的进度之 CEF客户端
.NET IoC模式依赖反转(DIP)、控制反转(Ioc)、依赖注入(DI)
vue+.netcore可支持业务代码扩展的开发框架 VOL.Vue 2.0版本发布
网友评论