• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号
登陆 注册

算法（第四版）C# 习题题解——2.3

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

写在前面

整个项目都托管在了 Github 上：https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp
查找更为方便的版本见：https://alg4.ikesnowy.com/
这一节内容可能会用到的库文件有 Quick，同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。

习题&题解

2.3.1

解答

2.3.2

解答

2.3.3

解答

N / 2
在快速排序中，一个元素要被交换，有以下两种情况
1.该元素是枢轴，在切分的最后一步被交换
2.该元素位于枢轴错误的一侧，需要被交换到另一侧去
注意，以上两种情况在一次切分中只会出现一次

首先来看第一种情况，如果一个元素变成了枢轴
那么在之后的切分中该元素会被排除，不存在后续的交换。
因此我们的目标应该是：
最大的元素总是出现在错误的一侧，同时切分的次数尽可能多。

接下来我们来思考如何构造这样的数组
由于我们针对的是最大的元素，因此「错误的一侧」就是枢轴的左侧。
为了使切分的次数尽可能多，我们需要保持最大值移动的距离尽量短。
但如果每次只移动一位的话，下一次切分时最大值就会变成枢轴
例如 4 10 3 5 6，枢轴为 4，交换后数组变为：
4 3 10 5 6
随后 4 和 3 交换
3 4 10 5 6
下一次切分时 10 会变成枢轴，不再参与后续的切分。
因此我们需要让最大值每次移动两个元素。

考虑下面的数组：
2 10 4 1 6 3 8 5 7 9
第一次切分的时候，枢轴为 2，10 和 1 进行交换
数组变为：
2 1 4 10 6 3 8 5 7 9
随后枢轴交换，数组变为：
1 2 4 10 6 3 8 5 7 9
第二次切分，枢轴为 4，10 和 3 进行交换。
1 2 4 3 6 10 8 5 7 9
随后枢轴交换 数组变为：
1 2 3 4 6 10 8 5 7 9
第三次切分，枢轴为 6，10 和 5 交换
1 2 3 4 6 5 8 10 7 9
随后枢轴交换，数组变为：
1 2 3 4 5 6 8 10 7 9
第四次切分，枢轴为 8，10 和 7 交换
1 2 3 4 5 6 8 7 10 9
枢轴交换，数组变为
1 2 3 4 5 6 7 8 10 9
最后一次切分，枢轴为 10，直接交换
1 2 3 4 5 6 7 8 9 10

我们可以总结出要构造这样的数组的模板
a2 max a3 a1
其中 a1 < a2 < a3 < max
max 每轮切分移动两格，总共切分 N/ 2 次。

另请参阅

Number of largest element exchanges for quicksort-Stack Overflow

2.3.4

解答

每次只让枢轴变为已排序，这就是最坏情况。
这种时候枢轴是当前子数组的最大值 / 最小值。
由于在我们的实现中总是取子数组的第一个元素作为枢轴。
因此一个已排序的数组可以达到最坏情况，比较次数达到 O(n^ 2)。
如果换作取最后一个元素，最坏情况会变成逆序数组。

我们的实现中如果碰到与枢轴相等的元素也会停止循环，
因此如果数组中有重复的元素会减少比较次数。

例如：

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

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

2.3.5

解答

官方实现：https://algs4.cs.princeton.edu/23quicksort/Sort2distinct.java.html

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

Quick 库

2.3.6

解答

运行结果如下：

代码

新建一个 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;
            }
        }
    }
}
另请参阅

Quick 库

2.3.7

解答

我讨厌数学= =

证明：
我们设 $ 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 库
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

解答

每次切分都会把数组*分，共切分 logN 次（二分法），每次切分比较 N 次（i 和 j 会一位一位地从两边向中间靠拢）。
共比较 NlogN 次。

2.3.9

解答

切分时，枢轴左侧都是小于（或等于）枢轴的，
右侧都是大于（或等于）枢轴的
只有两种主键值时，
第一次切分之后，某一侧的元素将全部相同
（如果枢轴选了较大的，那么右侧将全部相同，反之则左侧全部相同）

只有三种主键值时，和一般快速排序并无不同。
但如果第一次切分时选择了中间值作为枢轴，且中间值只有一个
那么只需要一次切分数组便会有序。

2.3.10

解答

切比雪夫不等式（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 \]

另请参阅

切比雪夫不等式到底是个什么概念? - 马同学的回答 - 知乎

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

解答

2.3.13

解答

快速排序先将数组分为 （小于枢轴）枢轴（大于枢轴）三部分，然后再分别递归的排序左右两部分数组。
在这里，我们可以将快速排序的递归树看作是一棵二叉搜索树（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 页找到。
QuickSort-纽约大学
《算法导论》中关于随机 BST 高度的证明（P321 Theorem12.4）
Introduction to Algorithms
也可以参考下面这个链接获得更详细的解释。
Proof that a randomly built binary search tree has logarithmic height-StackExchange

2.3.14

解答

中文版题目有误，详见官方勘误页面：https://algs4.cs.princeton.edu/errata/errata-printing3.php

假设 $ 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}) \end{align*} \]

根据调和级数的性质（$ \ln (n) < 1+ \frac{1}{2}+ \cdots + \frac{1}{n} < 1+\ln(n) $），可以得到结论：

\[E(X) < 2n \ln(n) \]

另请参阅

下面这个链接里的 3.4.2 节给出了解法。
lect0906 - 卡内基梅隆大学
如果还是不能理解为什么多次切分不影响概率，可以参考三门问题的解释：
蒙提霍尔问题 - 维基百科
蒙提霍尔问题（又称三门问题、山羊汽车问题）的正解是什么？- 知乎

2.3.15

解答

事实上只需要修改快速排序的切分方法，分两次进行切分。
首先选第一个螺母作为枢轴，找到对应的螺丝（$ 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

解答

官方实现见：https://algs4.cs.princeton.edu/23quicksort/QuickBest.java.html

类似于快速排序的结构，只要中点的两边都是最佳情况，那么整个数组就是最佳情况了。
具体方法是：
首先构造一个有序数组，
然后找到中点（作为枢轴），
对中点左右两侧子数组进行构造，
将选择的枢轴放到开始处(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

解答

按照题意修改代码即可，在调用 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");
        }
    }
}
另请参阅

Quick 库

2.3.18

解答

每次切分时都取前三个元素的中位数作为枢轴，这可以带来约 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;
            }
        }
    }
}
另请参阅

Quick 库

2.3.19

解答

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

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

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

代码

五取样快排

using System;
using System.Diagnostics;
using Quick;

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

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

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

            // 少于五个元素的数组直接进行插入排序
            if (hi - lo + 1 < 5)
            {
                int n = hi - lo + 1;
                for (int i = lo; i - lo < n; i++)
                {
                    for (int k = i; k > 0 && Less(a[k], a[k - 1]); --k)
                    {
                        Exch(a, k, k - 1);
                    }
                }

                return;
            }

            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分，返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;

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

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

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

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

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

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

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

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

鲜花
握手
雷人
路过
鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
More+
上一篇：
LeetCode144.BinaryTreePreorderTraversal二叉树的前序遍历C++发布时间：2022-07-14
下一篇：
【转】C#中??、?、?:、?.、?[]详解发布时间：2022-07-14
热门推荐
More+
热门话题
More+
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服（服务时间 9:00～18:00）

在线QQ客服
地址：深圳市南山区西丽大学城创智工业园
电邮：jeky_zhao#qq.com
移动电话：139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap