C#编程之算法（第四版）C#题解—

C#编程之算法（第四版）C#题解——2.1

小标 2018-12-28 来源：阅读 1194 评论 0

摘要：本文主要向大家介绍了C#编程之算法（第四版）C#题解——2.1，通过具体的内容向大家展示，希望对大家学习C#编程有所帮助。

本文主要向大家介绍了C#编程之算法（第四版）C#题解——2.1，通过具体的内容向大家展示，希望对大家学习C#编程有所帮助。

写在前面
整个项目都托管在了 Github 上：https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp
这一节内容可能会用到的库文件有 Sort和 SortData，同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。
习题&题解
2.1.1
题目
按照算法 2.1 所示轨迹的格式给出选择排序是如何将数组 E A S Y Q U E S T I O N 排序的。
解答

2.1.2
题目
在选择排序中，一个元素最多可能会被交换多少次？平均可能会被交换多少次？
解答
最多会被交换 n 次，只要将一个有序数列循环右移一位就可以构造这样的情况。
例如：

平均每个元素被交换了 N/N=1 次。（总共 N 个元素，总共发生了 N 次交换）

2.1.3
题目
构造一个含有 N 个元素的数组，使选择排序（算法 2.1）运行过程中 a[j] < a[min] （由此 min 会不断更新）成功的次数最大。
解答
你需要一个逆序的数组。
例如：9 8 7 6 5 4 3 2 1
i=0 条件满足 8 次，1 和 9 交换，1 8 7 6 5 4 3 2 9。
i=1 条件满足 6 次，2 和 8 交换，1 2 7 6 5 4 3 8 9。
i=2 条件满足 4 次，3 和 7 交换，1 2 3 6 5 4 7 8 9。
i=3 条件满足 2 次，4 和 6 交换。1 2 3 4 5 6 7 8 9。
一共满足了 8+6+4+2=20 次

2.1.4
题目
按照算法 2.2 所示轨迹的格式给出插入排序是如何将数组 E A S Y Q U E S T I O N 排序的。
解答

2.1.5
题目
构造一个含有 N 个元素的数组，使插入排序（算法 2.2）运行过程中内循环（for）的两个判断结果总是假。
解答
条件是：

j > 0 && less(a[j], a[j - 1])

第一个条件属于循环计数用的条件，与数组元素无关；
第二个条件当 a[j] 和 a[j - 1] 是一组逆序对时满足，因此这个条件总是为假 = 数组没有逆序对 = 数组有序。
因此只要输入已经排好序的数组即可。
逆序对：指序列中顺序相反的两个数，例如 1 2 3 4 5 7 6 8 9 中的 7 6。

2.1.6
题目
在所有主键都相同时，选择排序和插入排序谁更快？
解答
插入排序更快。
选择排序无论如何都需要 n + (n-1) + (n-2) + … + 1 = n^2/2 次比较。
插入排序在这种情况下只需要 n 次比较。（所有主键相同 = 数组已排序）

2.1.7
题目
对于逆序数组，选择排序和插入排序谁更快？
解答
假设比较的开销小于等于交换的开销，此时选择排序更快，具体比较见下表。

比较次数
交换次数

插入排序
~N^2/2
~N^2/2

选择排序
~N^2/2
N

2.1.8
题目
假设元素只可能有三种值，使用插入排序处理这样一个随机数组的运行时间是线性的还是平方级别的？或是介于两者之间？
解答
平方级别。
如果数组中元素各不相同，那么这个结论很容易证明（一般的插入排序）。
接下来我们证明有重复元素的情况下，这个结论仍然成立：
首先对于插入排序过程中的某一时刻，我们有下图这样的一般情况：

其中，1，2，3 分别代表三种不同的取值以及其先后顺序。
假设这是第 i 次插入前，如果第 i 次插入的是 1，我们需要交换 b+c 次，插入 2 则需要交换 c 次，插入 3 则不需要交换。
根据题意，这是一个随机数组，我们假设其为均匀分布，那么三种取值的出现几率相等。
第 i 次插入所需要的平均交换次数即为：

第 i 次插入后，b + 2c 视插入的元素不同会出现不同的变化：
如果插入的是 1，那么 b+2c 的值不会变化。
如果插入的是 2，那么 b+2c 的值增加 1。
如果插入的是 3，那么 b+2c 的值增加 2。
同样由于三种取值的概率相等，我们得出第 i + 1 次插入平均需要交换的次数为：

也就是说，平均每次插入都会使下一次插入的交换次数增加 1/3。
令 i=0，此时交换次数为 0，i+1 的交换次数即为 1/3，i+2 的交换次数即为 2/3，以此类推。
我们可以得出总交换次数：

由此证明，在元素取值为 3 种且出现概率相等时，插入排序的交换开销时平方级别的。
比较开销和交换开销类似，一般情况下比较次数=交换次数+1，除非插入的数是已知最小的数（移动到最左侧），这个时候比较次数和交换次数相等。
因此比较次数=交换次数+N-e，e 是一个不大于 N 的数，代表插入的数是已知最小的数这种情况发生的次数。
根据上式可以得出结论：在元素取值为 3 种且出现概率相等时，插入排序的比较开销也是平方级别的。
综合两个结论即可证明插入排序的开销在题目描述的情况下是平方级别的。
证明完毕。

2.1.9
题目
按照算法 2.3 所示轨迹的格式给出希尔排序是如何将数组 E A S Y S H E L L S O R T Q U E S T I O N 排序的。
解答

2.1.10
题目
在希尔排序中为什么在实现 h 有序时不使用选择排序？
解答
对于部分有序的数组，插入排序比选择排序快。
这个结论可以在中文版 P158，英文版 P252 找到。

2.1.11
题目
将希尔排序中实时计算递增序列改为预先计算并存储在一个数组中。
解答
希尔排序的官方实现：https://algs4.cs.princeton.edu/21elementary/Shell.java.html
只要稍作修改即可，详情见代码。
代码

///

/// 利用希尔排序将数组按升序排序。
///

///

需要排序的数组。
public override void Sort

(T[] a)
        {
            int n = a.Length;
            int[] h = new int[2];   // 预先准备好的 h 值数组

            int hTemp = 1;
            int sequenceSize = 0;
            for (sequenceSize = 0; hTemp < n; sequenceSize++)
            {
                if (sequenceSize >= h.Length)  // 如果数组不够大则双倍扩容
                {
                    int[] expand = new int[h.Length * 2];
                    for (int j = 0; j < h.Length; j++)
                    {
                        expand[j] = h[j];
                    }
                    h = expand;
                }
                h[sequenceSize] = hTemp;
                hTemp = hTemp * 3 + 1;
            }

            for (int t = sequenceSize - 1; t >= 0; t--)
            {
                for (int i = h[t]; i < n; i++)
                {
                    for (int j = i; j >= h[t] && Less(a[j], a[j - h[t]]); j -= h[t])
                    {
                        Exch(a, j, j - h[t]);
                    }
                }
                Debug.Assert(IsHSorted(a, h[t]));
            }
            Debug.Assert(IsSorted(a));
        }

2.1.12
题目
令希尔排序打印出递增序列的每个元素所带来的比较次数和数组大小的比值。编写一个测试用例对随机 Double 数组进行希尔排序，验证该值是一个小常数，数组大小按照 10 的幂次递增，不小于 100。
解答
结果截图如下，同一个 h 值对应的比值在数组大小不同时保持为一个小常数：

代码

class Program
{
    // 查看最后结果
    // 可以发现相同的 h 在数组大小不同时所产生的比值十分接近。
    static void Main(string[] args)
    {
        Random random = new Random();
        ShellSort sort = new ShellSort();

        int size = 100;
        for (int i = 0; i < 5; i++)
        {
            double[] a = new double[size];
            for (int j = 0; j < size; j++)
            {
                a[j] = random.NextDouble() * 100;
            }
            Console.WriteLine("ArraySize:" + size);
            sort.Sort(a);
            size *= 10;
        }
    }
}

2.1.13
题目
纸牌排序。
说说你会如何将一副扑克牌按花色排序（花色排序是黑桃、红桃、梅花和方片），限制条件是所有牌都是背面朝上排成一列，而你一次只能翻看两张牌或者交换两张牌（保持背面朝上）。
解答
可以用冒泡排序做，具体方法如下：
翻一二两张，是逆序对就交换，否则什么也不做
翻二三两张，是逆序对就交换，否则什么也不做
一直到最后，可以保证最右侧的是最大花色的牌
然后不断重复上述过程，就可以完全排序

2.1.14
题目
出列顺序。
说说你会如何将一副扑克牌排序，限制条件是只能查看最上面的两张牌，交换最上面的两张牌，或是将最上面的一张牌放到这摞牌的最下面。
解答
用一种类似于冒泡的方法做，具体步骤为：

重复以下步骤，直到全部完成一遍之后没有发生交换
    重复以下步骤 n-1 次
        如果顶端两张牌逆序，那么交换它们。
        将第一张牌放到牌堆底部。

具体步骤图：

我们将牌排成一个环，用一支笔隔开，这里我们标记笔的左侧是牌堆顶部，右侧是牌堆底部。
那么我们能做的三个操作在这里即为：
查看最上面两张牌 = 从笔的位置开始，逆时针查看两张牌。
交换最上面两张牌 = 从笔的位置开始，逆时针选择两张牌并交换。
将最上面的一张牌放到最下面 = 将笔的位置逆时针移动一位。

下面我们开始执行开始说过的操作，目标顺序是自顶向下从小到大排列。
初始情况如图所示：

梅花7 和红桃4 不是逆序对，直接将笔逆时针移动一位。

红桃4 和黑桃6 不是逆序对，我们将笔逆时针移动一位。

再看黑桃6 和方片A，是逆序对，我们交换并将笔逆时针移动一位。

再看黑桃6 和红桃J，是逆序对，我们交换并将笔逆时针移动一位。

现在我们已经操作了 4 次，内部循环结束，我们将笔放回初始位置。

这样一次循环之后，我们就把最大的牌放在了最下面，依次类推即可完全排序。

2.1.15
题目
昂贵的交换。
一家货运公司的一位职工得到了一项任务，需要将若干大货箱按照发货时间摆放。比较发货时间很容易（对照标签即可），但将两个货箱交换位置则很困难（移动麻烦）。仓库已经快满了，只有一个空闲的仓位。这位职员应该使用哪种排序算法呢？
解答
选择排序
交换（也就是 Exch() 方法）需要一个额外空间，这里的条件满足。
现在我们应该使交换次数最少，选择排序只需要 N 次交换，比插入排序平均 N^2/4 少（N > 2）。

2.1.16
题目
验证。
编写一个 check() 方法，调用 sort() 对任意数组排序。如果排序成功而且数组中的所有对象均没有被修改则返回 true，否则返回 false。不要假设 sort() 只能通过 exch() 来移动数据，可以信任并使用 Array.sort()。
解答
如果移动数据时新建了对象，那么虽然值没有改变，但是数组中的对象被修改了。
代码
插入排序中的 Exch() 换成了如下方式：

string temp = new string(s[i].ToCharArray());
s[i] = s[min];
s[min] = temp;

全部程序代码如下：

using System;

namespace _2._1._16
{
    /*
     * 2.1.16
     *
     * 验证。
     * 编写一个 check() 方法，
     * 调用 sort() 对任意数组排序。
     * 如果排序成功而且数组中的所有对象均没有被修改则返回 true，
     * 否则返回 false。
     * 不要假设 sort() 只能通过 exch() 来移动数据，
     * 可以信任并使用 Array.sort()。
     *
     */
    public class Program
    {
        static void Main(string[] args)
        {
            string[] test = new string[5] { "a", "b", "d", "c", "e" };
            Console.WriteLine(CheckArraySort(test));
            Console.WriteLine(CheckSelectionSort(test));
        }

        ///

/// 测试 Array.Sort() 方法。
///

        /// 用于测试的数组。
        /// 如果数组对象没有改变，返回 true，否则返回 false。
        static bool CheckArraySort(string[] a)
        {
            string[] backup = new string[a.Length];
            a.CopyTo(backup, 0);

            Array.Sort(a);

            foreach (string n in a)
            {
                bool isFind = false;
                for (int i = 0; i < a.Length; i++)
                {
                    if (ReferenceEquals(n, backup[i]))
                    {
                        isFind = true;
                        break;
                    }
                }
                if (!isFind)
                {
                    return false;
                }
            }

            return true;
        }

        ///

/// 测试选择排序。
///

        /// 用于测试的数组。
        /// 如果数组对象没有改变，返回 true，否则返回 false。
        static bool CheckSelectionSort(string[] a)
        {
            string[] backup = new string[a.Length];
            a.CopyTo(backup, 0);

            SelectionSort(a);

            foreach (string n in a)
            {
                bool isFind = false;
                for (int i = 0; i < a.Length; i++)
                {
                    if (ReferenceEquals(n, backup[i]))
                    {
                        isFind = true;
                        break;
                    }
                }
                if (!isFind)
                {
                    return false;
                }
            }

            return true;
        }

        ///

/// 选择排序，其中的交换部分使用新建对象并复制的方法。
///

        /// 用于排序的数组。
        public static void SelectionSort(string[] s)
        {
            for (int i = 0; i < s.Length; i++)
            {
                int min = i;
                for (int j = i + 1; j < s.Length; j++)
                {
                    if (s[j].CompareTo(s[min]) < 0)
                    {
                        min = j;
                    }
                }
                string temp = new string(s[i].ToCharArray());
                s[i] = s[min];
                s[min] = temp;
            }
        }
    }
}

2.1.17
题目
动画。
修改插入排序和选择排序的代码，使之将数组内容绘制成正文中所示的棒状图。在每一轮排序后重绘图片来产生动画效果，并以一张“有序”的图片作为结束，即所有的圆棒均已按照高度有序排列。提示：使用类似于正文中的用例来随机生成 Double 值，在排序代码的适当位置调用 show() 方法，并在 show() 方法中清理画布并绘制棒状图。
解答
选择排序：

插入排序：

代码
使用一个 timer 按一定时间重绘数组，排序算法里面一次循环后等待一段时间再进行下一次循环。
这里排序算法是另开线程运行的，防止 Sleep 的时候让程序无响应。
选择排序：

using System;
using System.Drawing;
using System.Windows.Forms;
using System.Threading;

namespace _2._1._17
{
    public partial class Form2 : Form
    {
        double[] randomDoubles;
        public Form2(int N)
        {
            InitializeComponent();
            this.randomDoubles = new double[N];
            Random random = new Random();
            for (int i = 0; i < N; i++)
            {
                this.randomDoubles[i] = random.NextDouble() * 0.8 + 0.2;
            }
            drawPanel();

            this.timer1.Interval = 60;
            this.timer1.Start();

            Thread thread = new Thread(new ThreadStart(this.SelectionSort));
            thread.IsBackground = true;
            thread.Start();
        }

        ///

/// 选择排序。
///

        private void SelectionSort()
        {
            for (int i = 0; i < this.randomDoubles.Length; i++)
            {
                int min = i;
                for (int j = i; j < this.randomDoubles.Length; j++)
                {
                    if (this.randomDoubles[min] > this.randomDoubles[j])
                    {
                        min = j;
                    }
                }
                double temp = this.randomDoubles[i];
                this.randomDoubles[i] = this.randomDoubles[min];
                this.randomDoubles[min] = temp;
                Thread.Sleep(1000);
            }
        }

        ///

/// 在屏幕上用柱形图绘制数组。
///

        private void drawPanel()
        {
            Graphics graphics = this.CreateGraphics();
            graphics.Clear(this.BackColor);
            graphics.TranslateTransform(0, this.Height);
            graphics.ScaleTransform(1, -1);
            Rectangle clientRect = this.ClientRectangle;
            Rectangle drawRect = new Rectangle(clientRect.X + 10, clientRect.Y + 10, clientRect.Width - 10, clientRect.Height - 10);

            PointF[] barX = new PointF[this.randomDoubles.Length];
            float unitX = (float)drawRect.Width / this.randomDoubles.Length;
            unitX -= 4;

            barX[0] = new PointF(4, drawRect.Top);
            for (int i = 1; i < this.randomDoubles.Length; i++)
            {
                barX[i] = new PointF(2 + unitX + barX[i - 1].X, drawRect.Top);
            }

            RectangleF[] bars = new RectangleF[this.randomDoubles.Length];
            for (int i = 0; i < this.randomDoubles.Length; i++)
            {
                SizeF size = new SizeF(unitX, (float)this.randomDoubles[i] * drawRect.Height);
                bars[i] = new RectangleF(barX[i], size);
            }

            graphics.FillRectangles(Brushes.Black, bars);
            graphics.Dispose();
        }

        private void timer1_Tick(object sender, EventArgs e)
        {
            drawPanel();
        }
    }
}

插入排序：

using System;
using System.Drawing;
using System.Windows.Forms;
using System.Threading;

namespace _2._1._17
{
    public partial class Form3 : Form
    {
        double[] randomDoubles;
        public Form3(int N)
        {
            InitializeComponent();
            this.randomDoubles = new double[N];
            Random random = new Random();
            for (int i = 0; i < N; i++)
            {
                this.randomDoubles[i] = random.NextDouble() * 0.8 + 0.2;
            }
            drawPanel();

            this.timer1.Interval = 60;
            this.timer1.Start();

            Thread thread = new Thread(new ThreadStart(this.InsertionSort));
            thread.IsBackground = true;
            thread.Start();
        }

        ///

/// 插入排序。
///

        private void InsertionSort()
        {
            for (int i = 0; i < this.randomDoubles.Length; i++)
            {
                for (int j = i; j > 0 && this.randomDoubles[j] < this.randomDoubles[j - 1]; j--)
                {
                    double temp = this.randomDoubles[j];
                    this.randomDoubles[j] = this.randomDoubles[j - 1];
                    this.randomDoubles[j - 1] = temp;
                    Thread.Sleep(500);
                }
            }
        }

        ///

/// 在屏幕上用柱形图绘制数组。
///

        private void drawPanel()
        {
            Graphics graphics = this.CreateGraphics();
            graphics.Clear(this.BackColor);
            graphics.TranslateTransform(0, this.Height);
            graphics.ScaleTransform(1, -1);
            Rectangle clientRect = this.ClientRectangle;
            Rectangle drawRect = new Rectangle(clientRect.X + 10, clientRect.Y + 10, clientRect.Width - 10, clientRect.Height - 10);

            PointF[] barX = new PointF[this.randomDoubles.Length];
            float unitX = (float)drawRect.Width / this.randomDoubles.Length;
            unitX -= 4;

            barX[0] = new PointF(4, drawRect.Top);
            for (int i = 1; i < this.randomDoubles.Length; i++)
            {
                barX[i] = new PointF(2 + unitX + barX[i - 1].X, drawRect.Top);
            }

            RectangleF[] bars = new RectangleF[this.randomDoubles.Length];
            for (int i = 0; i < this.randomDoubles.Length; i++)
            {
                SizeF size = new SizeF(unitX, (float)this.randomDoubles[i] * drawRect.Height);
                bars[i] = new RectangleF(barX[i], size);
            }

            graphics.FillRectangles(Brushes.Black, bars);
            graphics.Dispose();
        }

        private void timer1_Tick(object sender, EventArgs e)
        {
            drawPanel();
        }
    }
}

2.1.18
题目
可视轨迹。修改你为上一题给出的解答，为插入排序和选择排序生成和正文中类似的可视轨迹。提示：使用 setYscale() 函数是一个明智的选择。附加题：添加必要的代码，与正文中的图片一样用红色和灰色强调不同角色的元素。
解答
选择排序

插入排序

代码
与上题类似，但要特别标出移动的元素。
选择排序：

using System;
using System.Drawing;
using System.Windows.Forms;
using System.Threading;

namespace _2._1._18
{
    public partial class Form2 : Form
    {
        double[] randomDoubles;
        int sortI;
        int sortJ;
        int sortMin;
        public Form2(int N)
        {
            InitializeComponent();
            this.randomDoubles = new double[N];
            Random random = new Random();
            for (int i = 0; i < N; i++)
            {
                this.randomDoubles[i] = random.NextDouble() * 0.8 + 0.2;
            }
        }

        ///

/// 选择排序。
///

        private void SelectionSort()
        {
            for (this.sortI = 0; this.sortI < this.randomDoubles.Length; this.sortI++)
            {
                this.sortMin = this.sortI;
                for (this.sortJ = this.sortI; this.sortJ < this.randomDoubles.Length; this.sortJ++)
                {
                    if (this.randomDoubles[this.sortMin] > this.randomDoubles[this.sortJ])
                    {
                        this.sortMin = this.sortJ;
                    }
                }
                drawPanel();
                double temp = this.randomDoubles[this.sortI];
                this.randomDoubles[this.sortI] = this.randomDoubles[this.sortMin];
                this.randomDoubles[this.sortMin] = temp;
                Thread.Sleep(1000);
            }
        }

        ///

/// 绘制柱形图。
///

        private void drawPanel()
        {
            Graphics graphics = this.CreateGraphics();
            graphics.Clear(this.BackColor);
            graphics.TranslateTransform(0, this.Height);
            graphics.ScaleTransform(1, -1);
            Rectangle clientRect = this.ClientRectangle;
            Rectangle drawRect = new Rectangle(clientRect.X + 10, clientRect.Y + 10, clientRect.Width - 10, clientRect.Height - 10);

            PointF[] barX = new PointF[this.randomDoubles.Length];
            float unitX = (float)drawRect.Width / this.randomDoubles.Length;
            unitX -= 4;

            barX[0] = new PointF(4, drawRect.Top);
            for (int i = 1; i < this.randomDoubles.Length; i++)
            {
                barX[i] = new PointF(2 + unitX + barX[i - 1].X, drawRect.Top);
            }

            RectangleF[] bars = new RectangleF[this.randomDoubles.Length];
            for (int i = 0; i < this.randomDoubles.Length; i++)
            {
                SizeF size = new SizeF(unitX, (float)this.randomDoubles[i] * drawRect.Height);
                bars[i] = new RectangleF(barX[i], size);
            }

            for (int i = 0; i < bars.Length; i++)
            {
                if (i == this.sortMin)
                {
                    graphics.FillRectangle(Brushes.Red, bars[i]);
                }
                else if (i < this.sortI)
                {
                    graphics.FillRectangle(Brushes.Gray, bars[i]);
                }
                else
                {
                    graphics.FillRectangle(Brushes.Black, bars[i]);
                }
            }
            graphics.Dispose();
        }

        private void Form2_Shown(object sender, EventArgs e)
        {
            SelectionSort();
        }
    }
}

插入排序

using System;
using System.Drawing;
using System.Windows.Forms;
using System.Threading;

namespace _2._1._18
{
    public partial class Form3 : Form
    {
        double[] randomDoubles;
        int sortI;
        int sortJ;
        int n = 0;
        public Form3(int N)
        {
            InitializeComponent();
            this.randomDoubles = new double[N];
            Random random = new Random();
            for (int i = 0; i < N; i++)
            {
                this.randomDoubles[i] = random.NextDouble() * 0.8 + 0.2;
            }
        }

        ///

/// 插入排序。
///

        private void InsertionSort()
        {
            for (this.sortI = 0; this.sortI < this.randomDoubles.Length; this.sortI++)
            {
                for (this.sortJ = this.sortI; this.sortJ > 0 && this.randomDoubles[this.sortJ] < this.randomDoubles[this.sortJ - 1]; this.sortJ--)
                {
                    double temp = this.randomDoubles[this.sortJ];
                    this.randomDoubles[this.sortJ] = this.randomDoubles[this.sortJ - 1];
                    this.randomDoubles[this.sortJ - 1] = temp;
                }
                drawPanel();
                Thread.Sleep(1000);
            }
        }

        ///

/// 绘制柱形图。
///

        private void drawPanel()
        {
            Graphics graphics = this.CreateGraphics();
            graphics.Clear(this.BackColor);
            graphics.TranslateTransform(0, this.Height);
            graphics.ScaleTransform(1, -1);
            Rectangle clientRect = this.ClientRectangle;
            Rectangle drawRect = new Rectangle(clientRect.X + 10, clientRect.Y + 10, clientRect.Width - 10, clientRect.Height - 10);

            PointF[] barX = new PointF[this.randomDoubles.Length];
            float unitX = (float)drawRect.Width / this.randomDoubles.Length;
            unitX -= 4;

            barX[0] = new PointF(4, drawRect.Top);
            for (int i = 1; i < this.randomDoubles.Length; i++)
            {
                barX[i] = new PointF(2 + unitX + barX[i - 1].X, drawRect.Top);
            }

            RectangleF[] bars = new RectangleF[this.randomDoubles.Length];
            for (int i = 0; i < this.randomDoubles.Length; i++)
            {
                SizeF size = new SizeF(unitX, (float)this.randomDoubles[i] * drawRect.Height);
                bars[i] = new RectangleF(barX[i], size);
            }

            for (int i = 0; i < bars.Length; i++)
            {
                if (i == this.sortJ)
                {
                    graphics.FillRectangle(Brushes.Red, bars[i]);
                }
                else if (i <= this.sorti="" i=""> this.sortJ)
                {
                    graphics.FillRectangle(Brushes.Black, bars[i]);
                }
                else
                {
                    graphics.FillRectangle(Brushes.Gray, bars[i]);
                }
            }
            graphics.Dispose();
        }

        private void Form3_Shown(object sender, EventArgs e)
        {
            InsertionSort();
        }
    }
}

2.1.19
题目
希尔排序的最坏情况。用 1 到 100 构造一个含有 100 个元素的数组并用希尔排序和递增序列 1 4 13 40 对其排序，使比较次数尽可能多。
解答
不得不说这道题意外的难。
放上论文链接：Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences)
这篇论文的第二章给出了一种构造最坏序列的方法，当然理想最坏（n^(3/2)）是达不到的了。
最后结果是 793 次。
代码
构造最坏情况的类

namespace _2._1._19
{
    class ShellSortWorstCase
    {
        ///

/// 获得最坏情况的数组。
///

        /// 数组大小。
        /// 希尔排序最坏情况的数组。
        public static int[] GetWorst(int n)
        {
            int l = 0;
            int?[] a = new int?[n + 1];

            for (int i = 0; i < a.Length; i++)
            {
                a[i] = null;
            }
            int P = 40;
            int PAddition = P;
            for (int i = 0; l < 100; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (a[j] == null && IsVisible(j, P))
                    {
                        l++;
                        a[j] = l;
                    }
                }
                P += PAddition;
            }

            int[] b = new int[n];
            for (int i = 0; i < n; i++)
            {
                b[i] = (int)a[i + 1];
            }

            return b;
        }

        ///

/// 确认 j - i 是不是在排序样板（Sorting Template）上。
///

        ///
        ///
        ///
        public static bool IsVisible(int i, int j)
        {
            int k = 0;
            while (k <= 100)
            {
                if (j - i >= k * 40 && j - i <= k * 41)
                    return true;
                k++;
            }
            return false;
        }
    }
}

会显示比较次数的 ShellSort 类

using System;
using System.Diagnostics;
using Sort;

namespace _2._1._19
{
    public class ShellSort : BaseSort
    {
        ///

/// 默认构造函数。
///

public ShellSort() { }

///

/// 利用希尔排序将数组按升序排序。
///

        /// 需要排序的数组。
        public override void Sort(T[] a)
        {
            int n = a.Length;
            int compareTime = 0;

            int h = 1;
            while (h < n / 3)
            {
                h = 3 * h + 1;
            }

            while (h >= 1)
            {
                for (int i = h; i < n; i++)
                {
                    for (int j = i; j >= h && Less(a[j], a[j - h]); j -= h)
                    {
                        Exch(a, j, j - h);
                        compareTime++;
                    }
                    compareTime++;
                }
                Debug.Assert(IsHSorted(a, h));
                h /= 3;
            }
            Console.WriteLine("CompareTime:" + compareTime);
            Debug.Assert(IsSorted(a));
        }

        ///

/// 检查一次希尔排序后的子数组是否有序。
///

        /// 排序后的数组。
        /// 子数组间隔。
        /// 是否有序。
        private bool IsHSorted(T[] a, int h) where T : IComparable
        {
            for (int i = h; i < a.Length; i++)
            {
                if (Less(a[i], a[i - h]))
                {
                    return false;
                }
            }
            return true;
        }
    }
}

Main 方法

using System;

namespace _2._1._19
{
    /*
     * 2.1.19
     *
     * 希尔排序的最坏情况。
     * 用 1 到 100 构造一个含有 100 个元素的数组并用希尔排序和
     * 递增序列 1 4 13 40 对其排序，
     * 使比较次数尽可能多。
     *
     */
    class Program
    {
        // 开放题，没有标准答案
        // 共参考的最差情况为 n^(3/2)
        // 本例共 793 次
        static void Main(string[] args)
        {
            int[] b;
            ShellSort sort = new ShellSort();
            b = ShellSortWorstCase.GetWorst(100);
            for (int i = 0; i < b.Length; i++)
            {
                Console.Write(b[i] + " ");
            }
            Console.WriteLine();
            sort.Sort(b);
        }
    }
}

2.1.20
题目
希尔排序的最好情况。最好情况是什么？证明你的结论。
解答
由于每次 h 排序都是插入排序，希尔排序最好情况就是插入排序的最好情况，也就是已排序的数组。

2.1.21
题目
可比较的交易。用我们的 Date 类（请见 2.1.1.4 节）作为模板扩展你的 Transaction 类（请见练习 1.2.13），实现 Comparable 接口，使交易能够按照金额排序。
解答
事实上官方给出来的 Date 类以及 Transaction 类都已经实现了这些接口。
Date 类：Date.java
Transaction 类：Transaction.java
代码

using System;
using Sort;

namespace _2._1._21
{
    /*
     * 2.1.21
     *
     * 可比较的交易。
     * 用我们的 Date 类（请见 2.1.1.4 节）
     * 作为模板扩展你的 Transaction 类（请见练习 1.2.13），
     * 实现 Comparable 接口，使交易能够按照金额排序。
     *
     */
    class Program
    {
        static void Main(string[] args)
        {
            Transaction[] a = new Transaction[4];
            a[0] = new Transaction("Turing 6/17/1990 644.08");
            a[1] = new Transaction("Tarjan 3/26/2002 4121.85");
            a[2] = new Transaction("Knuth 6/14/1999 288.34");
            a[3] = new Transaction("Dijkstra 8/22/2007 2678.40");

            Console.WriteLine("Unsorted");
            for (int i = 0; i < a.Length; i++)
            {
                Console.WriteLine(a[i]);
            }
            Console.WriteLine();

            Console.WriteLine("Sort by amount");
            InsertionSort insertionSort = new InsertionSort();
            insertionSort.Sort(a, new Transaction.HowMuchOrder());
            for (int i = 0; i < a.Length; i++)
                Console.WriteLine(a[i]);
            Console.WriteLine();
        }
    }
}

2.1.22
题目
交易排序测试用例。编写一个 SortTransaction 类，在静态方法 main() 中从标准输入读取一系列交易，将它们排序并在标准输出中打印结果。
解答
和上题类似，只要传入事先写好的比较器就可以了。
代码

using System;
using Sort;

namespace _2._1._22
{
    /*
     * 2.1.22
     *
     * 交易排序测试用例。
     * 编写一个 SortTransaction 类，
     * 在静态方法 main() 中从标准输入读取一系列交易，
     * 将它们排序并在标准输出中打印结果。
     *
     */
    class Program
    {
        static void Main(string[] args)
        {
            Transaction[] a = new Transaction[4];

            // 样例输入
            // Turing 6/17/1990 644.08
            // Tarjan 3/26/2002 4121.85
            // Knuth 6/14/1999 288.34
            // Dijkstra 8/22/2007 2678.40

            for (int i = 0; i < a.Length; i++)
            {
                string input = Console.ReadLine();
                a[i] = new Transaction(input);
            }

            InsertionSort insertionSort = new InsertionSort();

            Console.WriteLine("Unsorted");
            for (int i = 0; i < a.Length; i++)
            {
                Console.WriteLine(a[i]);
            }
            Console.WriteLine();

            Console.WriteLine("Sort by date");
            insertionSort.Sort(a, new Transaction.WhenOrder());
            for (int i = 0; i < a.Length; i++)
                Console.WriteLine(a[i]);
            Console.WriteLine();

            Console.WriteLine("Sort by customer");
            insertionSort.Sort(a, new Transaction.WhoOrder());
            for (int i = 0; i < a.Length; i++)
                Console.WriteLine(a[i]);
            Console.WriteLine();

            Console.WriteLine("Sort by amount");
            insertionSort.Sort(a, new Transaction.HowMuchOrder());
            for (int i = 0; i < a.Length; i++)
                Console.WriteLine(a[i]);
            Console.WriteLine();
        }
    }
}

2.1.23
题目
纸牌排序。请几位朋友分别将一副扑克牌排序（见练习2.1.13）。仔细观察并记录他们所使用的方法。
解答
方法多种多样。
首先是冒泡，见习题 2.1.13
插入排序也可以，如下：      从前往后不断翻牌，      对于翻到的每张牌，一直和之前的牌交换，      直至前面的牌比它小或者它已经是第一张了。
也可以用基数排序      从前向后依次翻开牌，      按照花色分成四堆，      然后按花色从大到小重新排列。
比较符合直觉的是选择排序      寻找最小的牌并放到第一位，      寻找范围向右缩减一位，重复上一步，直到最后一张。
还有其他方法，这里不再赘述。

2.1.24
题目
插入排序的哨兵。在插入排序的实现中先找出最小的元素并将其置于数组的最左边，这样就能去掉内循环的判断条件 j>0。使用 SortCompare 来评估这种做法的效果。注意：这是一种常见的规避边界测试的方法，能够省略判断条件的元素通常称为哨兵。
解答
如果使用官方的实现（InsertionX.java），最后结果可能会比一般插入排序慢，因为它是用冒泡的方法找最小值的。
一般做法是在待排序数组的最前端插入一个很小的值（比如 int.MinValue），然后对 a[1]~a[n] 排序。
代码
参考官方实现的插入排序：

using System.Collections.Generic;
using System.Diagnostics;
using Sort;

namespace _2._1._24
{
    ///

/// 插入排序类。
///

    public class InsertionSort : BaseSort
    {
        ///

/// 默认构造函数。
///

public InsertionSort() { }

///

/// 利用插入排序将数组按升序排序。
///

        /// 需要排序的数组。
        public override void Sort(T[] a)
        {
            int n = a.Length;
            int exchanges = 0;

            for (int i = n - 1; i > 0; i--)
            {
                if (Less(a[i], a[i - 1]))
                {
                    Exch(a, i, i - 1);
                    exchanges++;
                }
            }
            if (exchanges == 0)
                return;

            for (int i = 1; i < n; i++)
            {
                for (int j = i; Less(a[j], a[j - 1]); --j)
                {
                    Exch(a, j, j - 1);
                }
                Debug.Assert(IsSorted(a, 0, i));
            }
            Debug.Assert(IsSorted(a));
        }

        ///

/// 利用插入排序将数组排序。（使用指定比较器）
///

        /// 数组元素类型。
        /// 需要排序的数组。
        /// 比较器。
        public void Sort(T[] a, IComparer c)
        {
            int n = a.Length;
            int exchanges = 0;

            for (int i = n - 1; i > 0; i--)
            {
                if (Less(a[i], a[i - 1], c))
                {
                    Exch(a, i, i - 1);
                    exchanges++;
                }
            }
            if (exchanges == 0)
                return;

            for (int i = 1; i < n; i++)
            {
                for (int j = i; Less(a[j], a[j - 1], c); --j)
                {
                    Exch(a, j, j - 1);
                }
                Debug.Assert(IsSorted(a, 0, i, c));
            }
            Debug.Assert(IsSorted(a, c));
        }
    }
}

2.1.25
题目
不需要交换的插入排序。在插入排序的实现中使较大元素右移一位只需要访问一次数组（而不用使用 exch()）。使用 SortCompare 来评估这种做法的效果。
解答
使用依次赋值的方式腾出空间，到达指定位置之后再把元素插入。
看代码会方便理解一点。
官方实现：InsertionX.java。
代码

using System.Collections.Generic;
using System.Diagnostics;
using Sort;

namespace _2._1._25
{
    ///

/// 插入排序类。
///

    public class InsertionSort : BaseSort
    {
        ///

/// 默认构造函数。
///

public InsertionSort() { }

///

/// 利用插入排序将数组按升序排序。
///

        /// 需要排序的数组。
        public override void Sort(T[] a)
        {
            int n = a.Length;
            int exchanges = 0;

            for (int i = n - 1; i > 0 ; i--)
            {
                if (Less(a[i], a[i - 1]))
                {
                    Exch(a, i, i - 1);
                    exchanges++;
                }
            }
            if (exchanges == 0)
                return;

            for (int i = 2; i < n; i++)
            {
                int j = i;
                T v = a[i];
                while (Less(v, a[j - 1]))
                {
                    a[j] = a[j - 1];
                    j--;
                }
                a[j] = v;
                Debug.Assert(IsSorted(a, 0, i));
            }
            Debug.Assert(IsSorted(a));
        }

        ///

/// 利用插入排序将数组排序。（使用指定比较器）
///

        /// 数组元素类型。
        /// 需要排序的数组。
        /// 比较器。
        public void Sort(T[] a, IComparer c)
        {
            int n = a.Length;
            int exchanges = 0;

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C#.NET频道！

c#程序设计出入库仓库管理 c#窗体程序小游戏 c#入门经典第五版

本文由 @小标发布于职坐标。未经许可，禁止转载。