乐虎游戏|乐虎国际登录|欢迎你

算法(第四版)C#题解——2.1,

日期:2019-11-06编辑作者:计算机资讯

算法(第四版)C#题解——2.1,

写在前头

全套项目都托管在了 Github 上:

那风流洒脱节内容或者会用到的库文件有 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 会不断更新卡塔 尔(英语:State of Qatar)成功的次数最大。

解答

你要求三个逆序的数组。

例如: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 次插入平均须求交流的次数为:

也正是说,平均每一趟插入都会使下一遍插入的置换次数扩张 50%。

令 i=0,那个时候交流次数为 0,i+1 的置换次数即为 51%,i+2 的沟通次数即为 2/3,就那样推算。

咱们得以吸取总沟通次数:

因而表明,在要素取值为 3 种且现身可能率相等时,插入排序的沟通开支时平方级其余。

对比花销和置换花销相近,日常情状下相比次数=沟通次数+1,除非插入的数是已知最小的数(移动到最侧面卡塔尔,此时可比次数和置换次数等于。

由此相比较次数=调换次数+N-e,e 是二个不抢先 N 的数,代表插入的数是已知最小的数这种景况发生的次数。

借助上式能够得出结论:在要素取值为 3 种且现身可能率相等时,插入排序的可比花销也是平方级别的。

综述四个结论就能够验证插入排序的费用在标题陈述的状态下是平方级其余。

证实实现。

 

2.1.9

题目

信守算法 2.3 所示轨迹的格式给出Hill排序是如何将数组 E A S Y S H E L L S O Tiggo T Q U E S T I O N 排序的。

解答

 

2.1.10

题目

在Hill排序中缘何在促成 h 有序时不选取选用排序?

解答

对于部分有序的数组,插入排序比选取排序快。

其后生可畏结论能够在普通话版 P158, 克罗地亚共和国(Republic of Croatia卡塔 尔(阿拉伯语:قطر‎语版 P252 找到。

 

2.1.11

题目

将Hill排序中实时总计依次增加连串改为事先总括并蕴藏在二个数组中。

解答

Hill排序的官方实现:

比如稍作校勘就可以,实际情况见代码。

代码
/// <summary>
        /// 利用希尔排序将数组按升序排序。
        /// </summary>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(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

题目

令Hill排序打字与印刷出递增连串的各类元素所带动的相比较次数和数组大小的比值。
编排二个测量检验用例对随便 Double 数组实行Hill排序,验证该值是叁个小常数,数组大小依据 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

题目

高昂的置换。

一家货物运输集团的一人士工获得了意气风发项任务,要求将若干大货箱依据发货时间摆放。
比较发货时间十分轻巧(对照标签就能够卡塔 尔(英语:State of Qatar),但将四个货箱交流地点则很劳苦(移动麻烦卡塔 尔(阿拉伯语:قطر‎。
库房已经快满了,唯有四个空暇的仓位。那位高级干部应该利用哪一类排序算法呢?

解答

选料排序

换来(也正是 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));
        }

        /// <summary>
        /// 测试 Array.Sort() 方法。
        /// </summary>
        /// <param name="a">用于测试的数组。</param>
        /// <returns>如果数组对象没有改变,返回 true,否则返回 false。</returns>
        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;
        }

        /// <summary>
        /// 测试选择排序。
        /// </summary>
        /// <param name="a">用于测试的数组。</param>
        /// <returns>如果数组对象没有改变,返回 true,否则返回 false。</returns>
        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;
        }

        /// <summary>
        /// 选择排序,其中的交换部分使用新建对象并复制的方法。
        /// </summary>
        /// <param name="s">用于排序的数组。</param>
        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();
        }

        /// <summary>
        /// 选择排序。
        /// </summary>
        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);
            }
        }

        /// <summary>
        /// 在屏幕上用柱形图绘制数组。
        /// </summary>
        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();
        }

        /// <summary>
        /// 插入排序。
        /// </summary>
        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);
                }
            }
        }

        /// <summary>
        /// 在屏幕上用柱形图绘制数组。
        /// </summary>
        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;
            }
        }

        /// <summary>
        /// 选择排序。
        /// </summary>
        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);
            }
        }

        /// <summary>
        /// 绘制柱形图。
        /// </summary>
        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;
            }
        }

        /// <summary>
        /// 插入排序。
        /// </summary>
        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);
            }
        }

        /// <summary>
        /// 绘制柱形图。
        /// </summary>
        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

题目

Hill排序的最坏境况。
用 1 到 100 构造叁个分包 100 个因素的数组并用Hill排序和依次增加系列 1 4 13 40 对其排序,使比较次数尽大概多。

解答

只得说那道题意外的难。

放上散文链接:Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences)

那篇随想的第二章给出了意气风发种结构最坏系列的主意,当然能够最坏(n^(3/2)卡塔尔国是达不到的了。

提起底结果是 793 次。

代码

结构最坏意况的类

namespace _2._1._19
{
    class ShellSortWorstCase
    {
        /// <summary>
        /// 获得最坏情况的数组。
        /// </summary>
        /// <param name="n">数组大小。</param>
        /// <returns>希尔排序最坏情况的数组。</returns>
        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;
        }

        /// <summary>
        /// 确认 j - i 是不是在排序样板(Sorting Template)上。
        /// </summary>
        /// <param name="i"></param>
        /// <param name="j"></param>
        /// <returns></returns>
        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
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public ShellSort() { }

        /// <summary>
        /// 利用希尔排序将数组按升序排序。
        /// </summary>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(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));
        }

        /// <summary>
        /// 检查一次希尔排序后的子数组是否有序。
        /// </summary>
        /// <param name="a">排序后的数组。</param>
        /// <param name="h">子数组间隔。</param>
        /// <returns>是否有序。</returns>
        private bool IsHSorted<T>(T[] a, int h) where T : IComparable<T>
        {
            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

题目

Hill排序的最棒状态。最棒状态是何等?阐明您的结论。

解答

出于每回 h 排序都以插入排序,Hill排序最佳状态正是插入排序的最佳状态,也正是已排序的数组。

 

2.1.21

题目

可正如的交易。
用大家的 Date 类(请见 2.1.1.4 节卡塔 尔(英语:State of Qatar)作为模板扩张你的 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
{
    /// <summary>
    /// 插入排序类。
    /// </summary>
    public class InsertionSort : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public InsertionSort() { }

        /// <summary>
        /// 利用插入排序将数组按升序排序。
        /// </summary>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(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));
        }

        /// <summary>
        /// 利用插入排序将数组排序。(使用指定比较器)
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="c">比较器。</param>
        public void Sort<T>(T[] a, IComparer<T> 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
{
    /// <summary>
    /// 插入排序类。
    /// </summary>
    public class InsertionSort : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public InsertionSort() { }

        /// <summary>
        /// 利用插入排序将数组按升序排序。
        /// </summary>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(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));
        }

        /// <summary>
        /// 利用插入排序将数组排序。(使用指定比较器)
        /// </summary>
        /// <typeparam name="T">数组元素类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="c">比较器。</param>
        public void Sort<T>(T[] a, IComparer<T> 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 = 2; i < n; i++)
            {
                int j = i;
                T v = a[i];
                while (Less(v, a[j - 1], c))
                {
                    a[j] = a[j - 1];
                    j--;
                }
                a[j] = v;
                Debug.Assert(IsSorted(a, 0, i, c));
            }
            Debug.Assert(IsSorted(a, c));
        }
    }
}

 

2.1.26

题目

村生泊长数据类型。
编辑叁个能够处理 int 值的插入排序的新本子,
正如它和正文中所给出的贯彻(能够隐式地用自行李装运箱和拆箱转变 Integer 值并列排在一条线序卡塔尔国的习性。

解答

直白针对特殊值的话明确会快非常多。

代码

直白把泛型改成 int 就可以。

namespace _2._1._26
{
    /// <summary>
    /// 插入排序类。
    /// </summary>
    public class InsertionSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public InsertionSort() { }

        /// <summary>
        /// 利用插入排序将数组按升序排序。
        /// </summary>
        /// <param name="a">需要排序的数组。</param>
        public void Sort(int[] a)
        {
            int n = a.Length;
            for (int i = 0; i < n; i++)
            {
                for (int j = i; j > 0 && a[j] < a[j - 1]; --j)
                {
                    int t = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = t;
                }
            }
        }
    }
}

 

2.1.27

题目

Hill排序的用时是次平方级的。
在你的计算机上用 SortCompare 比较Hill排序和插入排序以至选用排序。
测量试验数组的朗朗上口遵照 2 的幂次依次增加,从 128 伊始。

解答

多少十分大的时候会相比明显。

代码
using System;
using Sort;

namespace _2._1._27
{
    /*
     * 2.1.27
     * 
     * 希尔排序的用时是次平方级的。
     * 在你的计算机上用 SortCompare 比较希尔排序和插入排序以及选择排序。
     * 测试数组的大小按照 2 的幂次递增,从 128 开始。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int n = 128;
            Random random = new Random();

            double shellPrev = 1;
            double insertionPrev = 1;
            double selectionPrev = 1;


            while (n < 65538)
            {
                int[] testShell = new int[n];
                int[] testInsertion = new int[n];
                int[] testSelection = new int[n];

                for (int i = 0; i < n; i++)
                {
                    testShell[i] = random.Next();
                    testInsertion[i] = testShell[i];
                    testSelection[i] = testShell[i];
                }

                Console.WriteLine("数组大小:" + n);

                Console.Write("Shell Sort:");
                double shellNow = SortCompare.Time(new ShellSort(), testShell);
                Console.WriteLine(shellNow + "ttNow/Prev=" + shellNow / shellPrev);
                Console.Write("Insertion Sort:");
                double insertionNow = SortCompare.Time(new InsertionSort(), testInsertion);
                Console.WriteLine(insertionNow + "tNow/Prev=" + insertionNow / insertionPrev);
                Console.Write("Selection Sort:");
                double selectionNow = SortCompare.Time(new SelectionSort(), testSelection);
                Console.WriteLine(selectionNow + "tNow/Prev=" + selectionNow / selectionPrev);
                Console.WriteLine();

                shellPrev = shellNow;
                insertionPrev = insertionNow;
                selectionPrev = selectionNow;

                n *= 2;
            }
        }
    }
}

 

2.1.28

题目

对等的主键。
对于主键仅也许取三种值的数组,评估和表明插入排序和接收排序的特性,假如三种主键值现身的可能率同样。

解答

插入排序会比选拔排序快上大多,当然增加品级不改变。

代码
using System;
using Sort;

namespace _2._1._28
{
    /*
     * 2.1.28
     * 
     * 相等的主键。
     * 对于主键仅可能取两种值的数组,
     * 评估和验证插入排序和选择排序的性能,
     * 假设两种主键值出现的概率相同。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int n = 1024;
            Random random = new Random();

            double insertionPrev = 1;
            double selectionPrev = 1;

            while (n < 65538)
            {
                int[] testInsertion = new int[n];
                int[] testSelection = new int[n];

                for (int i = 0; i < n; i++)
                {
                    testInsertion[i] = random.Next(2);
                    testSelection[i] = testInsertion[i];
                }

                Console.WriteLine("数组大小:" + n);

                Console.Write("Insertion Sort:");
                double insertionNow = SortCompare.Time(new InsertionSort(), testInsertion);
                Console.WriteLine(insertionNow + "tNow/Prev=" + insertionNow / insertionPrev);
                Console.Write("Selection Sort:");
                double selectionNow = SortCompare.Time(new SelectionSort(), testSelection);
                Console.WriteLine(selectionNow + "tNow/Prev=" + selectionNow / selectionPrev);
                Console.WriteLine();

                insertionPrev = insertionNow;
                selectionPrev = selectionNow;

                n *= 2;
            }
        }
    }
}

 

2.1.29

题目

Hill排序的多如牛毛类别。
经超过实际验比较算法 2.3 中所使用的依次增加类别和依次增加系列 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 64769, 146305, 260609
(那是经过类别 9×4^(k)-9×2^(k)+1 和 4^(k)-3×2^(k)+1 综合得到的卡塔 尔(阿拉伯语:قطر‎。
能够仿效练习 2.1.11。

解答

理当如此是难题给出的雨后春笋类别更加快啊,因为这几个行列就是作者建议来的嘛。
(故事集链接:

代码

纠正了须臾间 shellsort,让它遵照给定的 h 体系排序。

using System;
using System.Diagnostics;
using Sort;

namespace _2._1._29
{
    public class ShellSort : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public ShellSort() { }

        /// <summary>
        /// 利用希尔排序将数组按升序排序。
        /// </summary>
        /// <typeparam name="T">待排序的元素类型。</typeparam>
        /// <param name="a">待排序的数组。</param>
        /// <param name="h">需要使用的递增序列。</param>
        public void Sort<T>(T[] a, int[] h) where T : IComparable<T>
        {
            int n = a.Length;
            int t = 0;
            while (h[t] < a.Length)
            {
                t++;
                if (t >= h.Length)
                    break;
            }
            t--;

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

        /// <summary>
        /// 利用希尔排序将数组按升序排序。
        /// </summary>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(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));
        }

        /// <summary>
        /// 检查一次希尔排序后的子数组是否有序。
        /// </summary>
        /// <param name="a">排序后的数组。</param>
        /// <param name="h">子数组间隔。</param>
        /// <returns>是否有序。</returns>
        private bool IsHSorted<T>(T[] a, int h) where T : IComparable<T>
        {
            for (int i = h; i < a.Length; i++)
            {
                if (Less(a[i], a[i - h]))
                {
                    return false;
                }
            }
            return true;
        }
    }
}

 

2.1.30

题目

几何级数依次增加种类。
通过试验找到叁个 t,使得对于大小为 N=10^6 的即兴自由数组,使用依次增加类别1, [t], [t^2], [t^3], [t^4], ... 的Hill排序的运行时刻最短。
交由你能找到的八个至上 t 值以至对应的星罗棋布体系。
以下练习描述的是各样用于评估排序算法的测验用例。
它们的效用是用随便数据帮衬你加强对品质特点的精通。
随着命令行钦定的试验测量试验的增大,能够和 SortCompare 雷同在它们中利用 time() 函数来收获更可信赖的结果。
在随后的几节中大家会利用那个练习来评估更为复杂的算法。

解答

2,3,4

t 越大的话,根据这一个依次增加种类,10^6 次能够餍足的 h 也就越少。

代码
using System;
using Sort;
using System.Diagnostics;

namespace _2._1._30
{
    /*
     * 2.1.30
     * 
     * 几何级数递增序列。
     * 通过实验找到一个 t,使得对于大小为 N=10^6 的任意随机数组,
     * 使用递增序列 1, [t], [t^2], [t^3], [t^4], ... 的希尔排序的运行时间最短。
     * 给出你能找到的三个最佳 t 值以及相应的递增序列。
     * 以下练习描述的是各种用于评估排序算法的测试用例。
     * 它们的作用是用随机数据帮助你增进对性能特性的理解。
     * 随着命令行指定的实验测试的增大,
     * 可以和 SortCompare 一样在它们中使用 time() 函数来得到更精确的结果。
     * 在以后的几节中我们会使用这些练习来评估更为复杂的算法。
     * 
     */
    class Program
    {
        // t = 2, 3, 4
        // t 大于 10 之后,由于每次排序 h 缩减的太快,
        // 时间会越来越近似于直接插入排序。
        static void Main(string[] args)
        {
            int[] array = SortCompare.GetRandomArrayInt(1000000);
            int[] array2 = new int[array.Length];
            array.CopyTo(array2, 0);
            Stopwatch timer = new Stopwatch();

            long[] bestTimes = new long[3];
            long[] bestTs = new long[3];
            for (int i = 0; i < bestTimes.Length; i++)
            {
                bestTimes[i] = long.MaxValue;
                bestTs[i] = int.MaxValue;
            }

            long nowTime = 0;
            ShellSort shellSort = new ShellSort();

            for (int t = 2; t <= 1000000; t++)
            {
                Console.WriteLine(t);

                timer.Restart();
                shellSort.Sort(array, t);
                nowTime = timer.ElapsedMilliseconds;
                timer.Stop();
                Console.WriteLine("Elapsed Time:" + nowTime);
                for (int i = 0; i < bestTimes.Length; i++)
                {
                    Console.Write("t:" + bestTs[i]);
                    Console.WriteLine("tTime:" + bestTimes[i]);
                }
                if (bestTimes[2] > nowTime)
                {
                    bestTimes[2] = nowTime;
                    bestTs[2] = t;
                    Array.Sort(bestTimes, bestTs);
                }

                array2.CopyTo(array, 0);
            }

            for (int i = 0; i < bestTimes.Length; i++)
            {
                Console.Write("t:" + bestTs[i]);
                Console.Write("tTime:" + bestTimes[i]);
            }
        }
    }
}

 

2.1.31

题目

双倍测量检验。
编写三个可见对排序算法举办双倍测量检验的用例。
数组规模 N 的伊始值为 1000,排序后打字与印刷N、估摸排序用时、实际排序用时以致在 N 倍增之后一遍用时的百分比。
用这段程序验证在随便输入模型下插入排序和甄选排序的运维时刻都以平方级其余。
对Hill排序的天性做出推断并表达你的疑惑。

解答

这里截取数据量相当的大的时候的数据。

插入排序和抉择排序鲜明都以平方品级的。

Hill排序揣度是线性的,实际上要比线性大一些(次平方级卡塔 尔(阿拉伯语:قطر‎。

代码
using System;
using Sort;

namespace _2._1._31
{
    /*
     * 2.1.31
     * 
     * 双倍测试。
     * 编写一个能够对排序算法进行双倍测试的用例。
     * 数组规模 N 的起始值为 1000,
     * 排序后打印 N、估计排序用时、实际排序用时以及在 N 倍增之后两次用时的比例。
     * 用这段程序验证在随机输入模型下插入排序和选择排序的运行时间都是平方级别的。
     * 对希尔排序的性能做出猜想并验证你的猜想。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int N = 1000;

            InsertionSort insertion = new InsertionSort();
            SelectionSort selection = new SelectionSort();
            ShellSort shell = new ShellSort();

            double prevInsertion = 0;
            double prevSelection = 0;
            double prevShell = 0;

            for (int i = 0; i < 10; i++)
            {
                Console.WriteLine("N:" + N);
                int[] array = SortCompare.GetRandomArrayInt(N);
                int[] arrayBak = new int[N];
                array.CopyTo(arrayBak, 0);

                Console.WriteLine("tInsertion Sort");
                double now = SortCompare.Time(insertion, array);
                Console.WriteLine("ttActual Time(ms):" + now);
                if (i != 0)
                {
                    Console.WriteLine("ttEstimate Time(ms):" + prevInsertion * 4);
                    Console.WriteLine("ttRatio:" + now / prevInsertion);
                }
                prevInsertion = now;

                arrayBak.CopyTo(array, 0);

                Console.WriteLine("tSelection Sort");
                now = SortCompare.Time(selection, array);
                Console.WriteLine("ttActual Time(ms):" + now);
                if (i != 0)
                {
                    Console.WriteLine("ttEstimate Time(ms):" + prevSelection * 4);
                    Console.WriteLine("ttRatio:" + now / prevSelection);
                }
                prevSelection = now;

                arrayBak.CopyTo(array, 0);

                Console.WriteLine("tShell Sort");
                now = SortCompare.Time(shell, array);
                Console.WriteLine("ttActual Time(ms):" + now);
                if (i != 0)
                {
                    Console.WriteLine("ttEstimate Time(ms):" + prevShell * 2);
                    Console.WriteLine("ttRatio:" + now / prevShell);
                }
                prevShell = now;

                N *= 2;
            }

        }
    }
}

 

2.1.32

题目

运转时刻曲线图。
编写多少个测验用例,使用 StdDraw 在各个差别层面的人身自由输入下将算法的平分运营时刻绘制作而成一张曲线图。
莫无需加上生龙活虎三个命令行参数,请尽大概设计一个实用的工具。

解答

基本上皆以如此个样子:

代码
using System;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
using Sort;

namespace _2._1._32
{
    public partial class Form2 : Form
    {
        BaseSort sort;
        int n;
        double[] result;

        /// <summary>
        /// 构造一个绘图结果窗口。
        /// </summary>
        /// <param name="sort">用于做测试的排序算法。</param>
        /// <param name="n">用于测试的初始数据量。</param>
        public Form2(BaseSort sort, int n)
        {
            InitializeComponent();
            this.sort = sort;
            this.n = n;
            this.result = Test(n);
            this.timer1.Interval = 1000;
            this.timer1.Start();
        }

        /// <summary>
        /// 执行八次耗时测试,每次数据量翻倍。
        /// </summary>
        /// <param name="n">初始数据量。</param>
        /// <returns>测试结果数据。</returns>
        public double[] Test(int n)
        {
            double[] result = new double[8];
            for (int i = 0; i < result.Length; i++)
            {
                result[i] = SortCompare.TimeRandomInput(this.sort, n, 3);
                n *= 2;
            }
            return result;
        }

        /// <summary>
        /// 绘制曲线图。
        /// </summary>
        /// <param name="result">结果数组。</param>
        public void DrawPanel(double[] result)
        {
            Graphics graphics = this.CreateGraphics();
            graphics.TranslateTransform(0, this.ClientRectangle.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[] dataPoints = new PointF[result.Length];
            float unitX = (float)drawRect.Width / result.Length;
            float unitY = (float)(drawRect.Height / result.Max());
            SizeF pointSize = new SizeF(8, 8);
            for (int i = 0; i < result.Length; i++)
            {
                dataPoints[i] = new PointF(drawRect.Left + unitX * i, (float)(unitY * result[i]));
                graphics.FillEllipse(Brushes.Black, new RectangleF(dataPoints[i], pointSize));

            }
        }

        private void timer1_Tick(object sender, EventArgs e)
        {
            DrawPanel(this.result);
            this.timer1.Stop();
        }
    }
}

 

2.1.33

题目

分布图。
对此你为演练 2.1.33 给出的测量检验用例,
在一个说长道短循环中调用 sort() 方法将由第多个命令行参数内定大小的数组排序,
笔录每回排序的用时并动用 StdDraw 在图上画出富有平均运转时刻,应该能力所能达到收获一张周转时刻的布满图。

解答

此处每一次结果的 Y 轴地点都以随机生成的,那样图像会赏心悦目点。

X 轴代表消耗的时光。

选用排序:

插入排序:

Hill排序:

代码
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
using Sort;

namespace _2._1._33
{
    public partial class Form2 : Form
    {
        List<double> resultList;
        List<float> resultYList;
        Rectangle clientRect;
        Rectangle drawRect;

        BaseSort sort;
        int n;

        /// <summary>
        /// 构造一个绘制结果窗口。
        /// </summary>
        /// <param name="sort">用于测试的排序算法。</param>
        /// <param name="n">测试算法是生成的数据量。</param>
        public Form2(BaseSort sort, int n)
        {
            InitializeComponent();
            this.resultList = new List<double>();
            this.resultYList = new List<float>();
            this.clientRect = this.ClientRectangle;
            this.drawRect = new Rectangle(this.clientRect.X + 10, this.clientRect.Y + 10, this.clientRect.Width - 10, this.clientRect.Height - 10);
            this.sort = sort;
            this.n = n;
            this.timer1.Interval = 500;
            this.timer1.Start();
        }

        /// <summary>
        /// 执行一次测试并绘制图像。
        /// </summary>
        public void Test()
        {
            Random random = new Random();
            double[] array = SortCompare.GetRandomArrayDouble(this.n);
            double time = SortCompare.Time(this.sort, array);
            this.resultList.Add(time);
            this.resultYList.Add((float)(random.NextDouble() * this.drawRect.Height));
            DrawPanel(this.resultList.ToArray(), this.resultYList.ToArray());
        }

        /// <summary>
        /// 根据已有的数据绘制图像。
        /// </summary>
        /// <param name="result">耗时数据(X 轴)</param>
        /// <param name="resultY">Y 轴数据</param>
        public void DrawPanel(double[] result, float[] resultY)
        {
            Graphics graphics = this.CreateGraphics();
            graphics.Clear(this.BackColor);
            graphics.TranslateTransform(0, this.ClientRectangle.Height);
            graphics.ScaleTransform(1, -1);

            PointF[] dataPoints = new PointF[result.Length];
            float unitX = (float)(this.drawRect.Width / (result.Max() - result.Min()));
            double min = result.Min();
            SizeF pointSize = new SizeF(8, 8);
            for (int i = 0; i < result.Length; i++)
            {
                dataPoints[i] = new PointF((float)(unitX * (result[i] - min)), resultY[i]);
                graphics.FillEllipse(Brushes.Black, new RectangleF(dataPoints[i], pointSize));
            }
        }

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

 

2.1.34

题目

鲜有情景。
编写一个测量检验用例,调用 sort() 方法对实际选用中可能现身困难或极端气象的数组实行排序。
例如,数组只怕早已然是一动不动的,或是逆序的,数组中的全部主键相近,数组的主键唯有二种值,大小是 0 或 1的数组。

解答
代码
using System;
using Sort;

namespace _2._1._34
{
    /*
     * 2.1.34
     * 
     * 罕见情况。
     * 编写一个测试用例,
     * 调用 sort() 方法对实际应用中可能出现困难或极端情况的数组进行排序。
     * 比如,数组可能已经是有序的,
     * 或是逆序的,
     * 数组中的所有主键相同,
     * 数组的主键只有两种值,
     * 大小是 0 或 1 的数组。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            InsertionSort insertionSort = new InsertionSort();
            SelectionSort selectionSort = new SelectionSort();
            ShellSort shellSort = new ShellSort();

            // 逆序
            Console.WriteLine("逆序");
            Console.WriteLine("Insertion Sort Time: " + ReverseSortTest(insertionSort));
            Console.WriteLine("Selection Sort Time: " + ReverseSortTest(selectionSort));
            Console.WriteLine("Shell Sort Time: " + ReverseSortTest(shellSort));

            // 顺序
            Console.WriteLine("顺序");
            Console.WriteLine("Insertion Sort Time: " + SortedSortTest(insertionSort));
            Console.WriteLine("Selection Sort Time: " + SortedSortTest(selectionSort));
            Console.WriteLine("Shell Sort Time: " + SortedSortTest(shellSort));

            // 主键相同
            Console.WriteLine("主键相同");
            Console.WriteLine("Insertion Sort Time: " + EqualSortTest(insertionSort));
            Console.WriteLine("Selection Sort Time: " + EqualSortTest(selectionSort));
            Console.WriteLine("Shell Sort Time: " + EqualSortTest(shellSort));

            // 二元数组
            Console.WriteLine("二元数组");
            Console.WriteLine("Insertion Sort Time: " + BinarySortTest(insertionSort));
            Console.WriteLine("Selection Sort Time: " + BinarySortTest(selectionSort));
            Console.WriteLine("Shell Sort Time: " + BinarySortTest(shellSort));

            // 空数组
            Console.WriteLine("空数组");
            Console.WriteLine("Insertion Sort Time: " + ZeroArraySizeSort(insertionSort));
            Console.WriteLine("Selection Sort Time: " + ZeroArraySizeSort(selectionSort));
            Console.WriteLine("Shell Sort Time: " + ZeroArraySizeSort(shellSort));

            // 只有一个元素的数组
            Console.WriteLine("只有一个元素的数组");
            Console.WriteLine("Insertion Sort Time: " + OneArraySizeSort(insertionSort));
            Console.WriteLine("Selection Sort Time: " + OneArraySizeSort(selectionSort));
            Console.WriteLine("Shell Sort Time: " + OneArraySizeSort(shellSort));
        }

        /// <summary>
        /// 构造逆序数组并用其对指定输入算法进行测试。
        /// </summary>
        /// <param name="sort">需要做测试的算法。</param>
        /// <returns>算法耗时。</returns>
        static double ReverseSortTest(BaseSort sort)
        {
            int[] array = new int[10000];
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = array.Length - i;
            }

            return SortCompare.Time(sort, array);
        }

        /// <summary>
        /// 构造已排序的数组并用其对指定排序算法测试。
        /// </summary>
        /// <param name="sort">需要做测试的排序算法。</param>
        /// <returns>算法的耗时。</returns>
        static double SortedSortTest(BaseSort sort)
        {
            return SortCompare.TimeSortedInput(sort, 10000, 1);
        }

        /// <summary>
        /// 构造只有一个值的数组并用其对指定排序算法做测试。
        /// </summary>
        /// <param name="sort">需要做测试的排序算法。</param>
        /// <returns>算法的耗时。</returns>
        static double EqualSortTest(BaseSort sort)
        {
            int[] array = new int[10000];
            Random random = new Random();
            int num = random.Next();
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = num;
            }

            return SortCompare.Time(sort, array);
        }

        /// <summary>
        /// 构造只有两种取值的数组并用其对指定排序算法做测试。
        /// </summary>
        /// <param name="sort">需要做测试的排序算法。</param>
        /// <returns>排序算法的耗时。</returns>
        static double BinarySortTest(BaseSort sort)
        {
            int[] array = new int[10000];
            Random random = new Random();
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = random.Next(2);
            }

            return SortCompare.Time(sort, array);
        }

        /// <summary>
        /// 构造空数组并用其对指定排序算法做测试。
        /// </summary>
        /// <param name="sort">需要做测试的排序算法。</param>
        /// <returns>排序算法的耗时。</returns>
        static double ZeroArraySizeSort(BaseSort sort)
        {
            int[] array = new int[0];

            return SortCompare.Time(sort, array);
        }

        /// <summary>
        /// 构造只有一个元素的数组并用其对指定排序算法做测试。
        /// </summary>
        /// <param name="sort">需要做测试的排序算法。</param>
        /// <returns>排序算法的耗时。</returns>
        static double OneArraySizeSort(BaseSort sort)
        {
            int[] array = new int[1];
            Random random = new Random();
            array[0] = random.Next();

            return SortCompare.Time(sort, array);
        }
    }
}

 

2.1.35

题目

不均匀的可能率布满。编写二个测验用例,使用非均匀布满的可能率来变化随机排列的数目,富含:

评估并表明这么些输入数据对本节研商的算法的震慑。

解答

困难是什么样转换相符这个布满的随机数。

Java 的话官方给的 stdRandom 里面皆有相应的兑现。

结果:

代码

二种随机数的贯彻:

using System;

namespace Sort
{
    /// <summary>
    /// 静态类,包含用于生成排序算法测试数据的方法。
    /// </summary>
    public static class SortUtil
    {

        public static Random UniformGenerator = new Random();

        /// <summary>
        /// 产生符合正态分布的随机数。
        /// </summary>
        /// <param name="average">正态分布的期望值 μ。</param>
        /// <param name="standardDeviation">正态分布的标准差 σ。</param>
        /// <returns>符合正态分布的随机数。</returns>
        public static double Normal(double average, double standardDeviation)
        {
            double u1 = UniformGenerator.NextDouble();
            double u2 = UniformGenerator.NextDouble();

            double z0 = Math.Sqrt(-2.0 * Math.Log(u1)) * Math.Cos(Math.PI * 2 * u2);

            return z0 * standardDeviation + average;
        }

        /// <summary>
        /// 生成符合泊松分布的随机数。
        /// </summary>
        /// <param name="average">泊松分布的期望值 λ。</param>
        /// <returns>一个符合泊松分布的随机数。</returns>
        public static double Poission(double average)
        {
            double x = 0;
            double p = Math.Pow(Math.E, -average);
            double s = p;
            double u = UniformGenerator.NextDouble();
            do
            {
                x++;
                p *= average / x;
                s += p;
            } while (u > s);
            return x;
        }

        /// <summary>
        /// 生成符合几何分布的随机数。
        /// </summary>
        /// <param name="p">几何分布的概率 p,这应该是一个小于 1 的非负数。</param>
        /// <exception cref="ArgumentOutOfRangeException">概率不能大于 1.</exception>
        /// <returns>符合几何分布的随机数。</returns>
        public static double Geometry(double p)
        {
            if (p > 1)
            {
                throw new ArgumentOutOfRangeException("p", "概率不能大于 1");
            }

            double result;
            result = Math.Ceiling(Math.Log(1 - UniformGenerator.NextDouble()) / Math.Log(1 - p));

            return result;
        }

        /// <summary>
        /// 根据指定的几率数组产生符合离散分布的随机数。
        /// </summary>
        /// <param name="probabilities">各取值的可能性。</param>
        /// <returns>符合随机分布的随机整数。</returns>
        public static double Discrete(double[] probabilities)
        {
            if (probabilities == null)
            {
                throw new ArgumentNullException("Argument array is null");
            }

            double EPSION = 1E-14;
            double sum = 0;
            for (int i = 0; i < probabilities.Length; i++)
            {
                if (probabilities[i] <= 0)
                {
                    throw new ArgumentException("array entry " + i + " must be nonnegative:" + probabilities[i]);
                }

                sum += probabilities[i];
            }

            if (sum > 1.0 + EPSION || sum < 1.0 - EPSION)
            {
                throw new ArgumentException("sum of array entries does not equal 1.0:" + sum);
            }

            while (true)
            {
                double r = UniformGenerator.NextDouble();
                sum = 0.0;
                for (int i = 0; i < probabilities.Length; i++)
                {
                    sum += probabilities[i];
                    if (sum > r)
                    {
                        return i;
                    }
                }
            }
        }
    }
}

 

Main 方法:

using System;
using Sort;

namespace _2._1._35
{
    /*
     * 2.1.35
     * 
     * 不均匀的概率分布。编写一个测试用例,使用非均匀分布的概率来生成随机排列的数据,包括:
     * 高斯分布
     * 泊松分布
     * 几何分布
     * 离散分布(一种特殊情况见练习 2.1.28)。
     * 评估并验证这些输入数据对本节讨论的算法的影响。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            InsertionSort insertionSort = new InsertionSort();
            SelectionSort selectionSort = new SelectionSort();
            ShellSort shellSort = new ShellSort();
            int n = 10000;

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

            arrayInsertion.CopyTo(arraySelection, 0);
            arrayInsertion.CopyTo(arrayShell, 0);

            Console.WriteLine("Normal Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Selection: " + SortCompare.Time(selectionSort, arraySelection));
            Console.WriteLine("Shell: " + SortCompare.Time(shellSort, arrayShell));

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

            Console.WriteLine("Poission Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Selection: " + SortCompare.Time(selectionSort, arraySelection));
            Console.WriteLine("Shell: " + SortCompare.Time(shellSort, arrayShell));

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

            Console.WriteLine("Geometric Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Selection: " + SortCompare.Time(selectionSort, arraySelection));
            Console.WriteLine("Shell: " + SortCompare.Time(shellSort, arrayShell));

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

            Console.WriteLine("Discret Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Selection: " + SortCompare.Time(selectionSort, arraySelection));
            Console.WriteLine("Shell: " + SortCompare.Time(shellSort, arrayShell));
        }
    }
}

 

2.1.36

题目

不均匀的数额。编写一个测量检验用例,生成不均匀的测量试验数据,包蕴:

评估并证实那些输入数据对本节研讨的算法的天性的熏陶。

解答

最后结果:

代码
using System;
using Sort;

namespace _2._1._36
{
    /*
     * 2.1.36
     * 
     * 不均匀的数据。
     * 编写一个测试用例,
     * 生成不均匀的测试数据,包括:
     * 一半数据是 0,一半数据是 1
     * 一半数据是 0,1/4 是 1,1/4 是 2,以此类推
     * 一半数据是 0,一半是随机 int 值。
     * 评估并验证这些输入数据对本节讨论的算法的性能的影响。
     * 
     */
    class Program
    {
        // 选择排序的耗时与输入值的内容无关,不受影响。
        // 对于插入排序,以上几种情况都是重复值较多的情况,插入排序的速度会加快。
        // 希尔排序本质上也是插入排序,因此也会更快一些。
        static void Main(string[] args)
        {
            int n = 10000;
            InsertionSort insertionSort = new InsertionSort();
            SelectionSort selectionSort = new SelectionSort();
            ShellSort shellSort = new ShellSort();

            int[] arrayInsertion = new int[n];
            int[] arraySelection = new int[n];
            int[] arrayShell = new int[n];

            // 对照,完全随机
            arrayInsertion = HalfZeroHalfOne(n);
            arrayInsertion.CopyTo(arraySelection, 0);
            arrayInsertion.CopyTo(arrayShell, 0);

            Console.WriteLine("totally random");
            Console.WriteLine("Insertion Sort:" + SortCompare.TimeRandomInput(insertionSort, n, 1));
            Console.WriteLine("Selection Sort:" + SortCompare.TimeRandomInput(selectionSort, n, 1));
            Console.WriteLine("Shell Sort:" + SortCompare.TimeRandomInput(shellSort, n, 1));
            Console.WriteLine();

            // 一半是 0 一半是 1
            arrayInsertion = HalfZeroHalfOne(n);
            arrayInsertion.CopyTo(arraySelection, 0);
            arrayInsertion.CopyTo(arrayShell, 0);

            Console.WriteLine("half 0 and half 1");
            Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, arraySelection));
            Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, arrayShell));
            Console.WriteLine();

            // 一半是 0, 1/4 是 1, 1/8 是 2……
            arrayInsertion = HalfAndHalf(n);
            arrayInsertion.CopyTo(arraySelection, 0);
            arrayShell.CopyTo(arrayShell, 0);

            Console.WriteLine("half and half and half ...");
            Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, arraySelection));
            Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, arrayShell));
            Console.WriteLine();

            // 一半是 0,一半是随机 int 值
            arrayInsertion = HalfZeroHalfRandom(n);
            arrayInsertion.CopyTo(arraySelection, 0);
            arrayShell.CopyTo(arrayShell, 0);

            Console.WriteLine("half 0 half random");
            Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, arraySelection));
            Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, arrayShell));
        }

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

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

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

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

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

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

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

            Shuffle(array);

            return array;
        }

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

 

2.1.37

题目

风流倜傥对有序。编写贰个测验用例,生成都部队分有序数组,包罗:

评估并表明这几个输入数据对本节斟酌的算法的习性的震慑。

解答

十分重要说一后一次之个的完毕,把四个数组循环左移/右移三个人就可以。

代码
using System;
using System.Collections.Generic;
using Sort;

namespace _2._1._37
{
    /*
     * 2.1.37
     * 
     * 部分有序。
     * 编写一个测试用例,生成部分有序数组,包括:
     * 95% 有序,其余部分为随机值。
     * 所有元素和它们的正确位置的距离都不超过 10。
     * 5% 的元素随机分布在整个数组中,剩下的数据都是有序的。
     * 评估并验证这些输入数据对本节讨论的算法的性能的影响。
     * 
     */
    class Program
    {
        // 选择排序的性能只与数组大小有关,以上三种情况耗时都是近似的。
        // 插入排序的性能与逆序对数量有关,部分有序的情况下耗时会小于完全随机。
        // 希尔排序与插入排序类似。
        static void Main(string[] args)
        {
            InsertionSort insertionSort = new InsertionSort();
            SelectionSort selectionSort = new SelectionSort();
            ShellSort shellSort = new ShellSort();
            int n = 10000;
            int[] selectionArray = new int[n];
            int[] insertionArray = new int[n];
            int[] shellArray = new int[n];

            // 完全随机的对照
            Console.WriteLine("totally random");
            Console.WriteLine("Selection Sort:" + SortCompare.TimeRandomInput(selectionSort, n, 1));
            Console.WriteLine("Insertion Sort:" + SortCompare.TimeRandomInput(insertionSort, n, 1));
            Console.WriteLine("Shell Sort:" + SortCompare.TimeRandomInput(shellSort, n, 1));

            // 95% 有序,其余部分为随机值。
            selectionArray = Sorted95Random5(n);
            selectionArray.CopyTo(insertionArray, 0);
            selectionArray.CopyTo(shellArray, 0);

            Console.WriteLine("95% sorted + 5% random");
            Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, selectionArray));
            Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, insertionArray));
            Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, shellArray));

            // 所有元素和它们的正确位置的距离都不超过 10。
            selectionArray = RandomIn10(n);
            selectionArray.CopyTo(insertionArray, 0);
            selectionArray.CopyTo(shellArray, 0);

            Console.WriteLine("a sorted array that left shift 6 times");
            Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, selectionArray));
            Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, insertionArray));
            Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, shellArray));

            // 5% 的元素随机分布在整个数组中,剩下的数据都是有序的。
            selectionArray = RandomIn10(n);
            selectionArray.CopyTo(insertionArray, 0);
            selectionArray.CopyTo(shellArray, 0);

            Console.WriteLine("95% elements is sorted while 5% elements are placed randomly");
            Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, selectionArray));
            Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, insertionArray));
            Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, shellArray));
        }

        /// <summary>
        /// 生成 95% 有序,最后 5% 随机的 <see cref="int"/> 数组。
        /// </summary>
        /// <param name="n">数组的大小。</param>
        /// <returns>95% 有序,最后 5% 随机的 <see cref="int"/> 数组。</returns>
        static int[] Sorted95Random5(int n)
        {
            int[] array = new int[n];
            int randomStart = (int)(n * 0.05);
            Random random = new Random();

            for (int i = 0; i < n - randomStart; i++)
            {
                array[i] = i;
            }

            for (int i = n - randomStart; i < n; i++)
            {
                array[i] = random.Next();
            }
            return array;
        }

        /// <summary>
        /// 返回一个 <see cref="int"/> 数组,其中的每个元素和它的正确位置的距离都不超过 10。
        /// </summary>
        /// <param name="n">数组大小。</param>
        /// <returns>一个 <see cref="int"/> 数组,其中的每个元素和它的正确位置的距离都不超过 10。</returns>
        static int[] RandomIn10(int n)
        {
            Queue<int> array = new Queue<int>();
            Random random = new Random();

            for (int i = 0; i < n; i++)
            {
                array.Enqueue(i);
            }

            for (int i = 0; i < 6; i++)
            {
                array.Enqueue(array.Dequeue());
            }

            return array.ToArray();
        }

        /// <summary>
        /// 生成 5% 元素随机分布,剩余有序的 <see cref="int"/> 数组。
        /// </summary>
        /// <param name="n">需要生成的数组大小。</param>
        /// <returns>5% 元素随机分布,剩余有序的 <see cref="int"/> 数组。</returns>
        static int[] Shuffle5Percent(int n)
        {
            Random random = new Random();
            int percent5 = (int)(n * 0.05);

            int[] randomIndex = new int[percent5];
            for (int i = 0; i < percent5; i++)
            {
                randomIndex[i] = random.Next(percent5);
            }

            int[] randomValue = new int[percent5];
            for (int i = 0; i < percent5; i++)
            {
                randomValue[i] = randomIndex[i];
            }
            Shuffle(randomValue);

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

            for (int i = 0; i < percent5; i++)
            {
                array[randomIndex[i]] = randomValue[i];
            }

            return array;
        }

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

 

2.1.38

题目

不一致门类的因素。编写四个测量检验用例,生成由各类数据类型成分构成的数组,成分的主键值随机,包括:

评估并表明这个输入数据对本节商量的算法的性质的影响。

解答

此地完成了一个 Pair 类,用来排序。

每贰个因素都有照顾的 key 值和 value 值,排序时只利用 key 值举办排序。

代码
using System;
using Sort;

namespace _2._1._38
{
    /*
     * 2.1.38
     * 
     * 不同类型的元素。
     * 编写一个测试用例,生成由多种数据类型元素组成的数组,元素的主键值随机,包括:
     * 每个元素的主键均为 String 类型(至少长 10 个字符),并含有一个 double 值。
     * 每个元素的主键均为 double 类型,并含有 10 个 String 值(每个都至少长 10 个字符)。
     * 每个元素的主键均为 int 类型,并含有一个 int[20] 值。
     * 评估并验证这些输入数据对本节讨论的算法的性能的影响。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int n = 10000;

            double[] results = TestA(n);
            Console.WriteLine("string + double");
            Console.WriteLine("Insertion Sort:" + results[0]);
            Console.WriteLine("Selection Sort:" + results[1]);
            Console.WriteLine("Shell Sort:" + results[2]);

            results = TestB(n);
            Console.WriteLine("double + 10 string");
            Console.WriteLine("Insertion Sort:" + results[0]);
            Console.WriteLine("Selection Sort:" + results[1]);
            Console.WriteLine("Shell Sort:" + results[2]);

            results = TestC(n);
            Console.WriteLine("int + int[]");
            Console.WriteLine("Insertion Sort:" + results[0]);
            Console.WriteLine("Selection Sort:" + results[1]);
            Console.WriteLine("Shell Sort:" + results[2]);
        }

        /// <summary>
        /// 第一个测试,测试结果按照 Insertion, Selection, Shell 排序。
        /// </summary>
        /// <param name="n">测试的数组长度。</param>
        /// <returns>测试结果。</returns>
        static double[] TestA(int n)
        {
            InsertionSort insertionSort = new InsertionSort();
            SelectionSort selectionSort = new SelectionSort();
            ShellSort shellSort = new ShellSort();

            Random random = new Random();

            // 每个元素的主键均为 String 类型(至少长 10 个字符),并含有一个 double 值。
            Pair<string, double>[] array = new Pair<string, double>[n];
            Pair<string, double>[] arrayBak = new Pair<string, double>[n];
            for (int i = 0; i < n; i++)
            {
                array[i] = new Pair<string, double>(RandomString(20, random), random.NextDouble());
            }
            array.CopyTo(arrayBak, 0);

            double[] results = new double[3];
            results[0] = SortCompare.Time(insertionSort, array);
            arrayBak.CopyTo(array, 0);
            results[1] = SortCompare.Time(selectionSort, array);
            arrayBak.CopyTo(array, 0);
            results[2] = SortCompare.Time(shellSort, array);
            return results;
        }

        /// <summary>
        /// 第二个测试,测试结果按照 Insertion, Selection, Shell 排序。
        /// </summary>
        /// <param name="n">测试的数组长度。</param>
        /// <returns>测试结果。</returns>
        static double[] TestB(int n)
        {
            InsertionSort insertionSort = new InsertionSort();
            SelectionSort selectionSort = new SelectionSort();
            ShellSort shellSort = new ShellSort();

            Random random = new Random();

            // 每个元素的主键均为 double 类型,并含有 10 个 String 值(每个都至少长 10 个字符)。
            Pair<double, string[]>[] array = new Pair<double, string[]>[n];
            Pair<double, string[]>[] arrayBak = new Pair<double, string[]>[n];
            for (int i = 0; i < n; i++)
            {
                string[] temp = new string[10];
                for (int j = 0; j < 10; j++)
                {
                    temp[j] = RandomString(12, random);
                }
                array[i] = new Pair<double, string[]>(random.NextDouble(), temp);
            }
            array.CopyTo(arrayBak, 0);

            double[] results = new double[3];
            results[0] = SortCompare.Time(insertionSort, array);
            arrayBak.CopyTo(array, 0);
            results[1] = SortCompare.Time(selectionSort, array);
            arrayBak.CopyTo(array, 0);
            results[2] = SortCompare.Time(shellSort, array);
            return results;
        }

        /// <summary>
        /// 第三个测试,测试结果按照 Insertion, Selection, Shell 排序。
        /// </summary>
        /// <param name="n">测试的数组长度。</param>
        /// <returns>测试结果。</returns>
        static double[] TestC(int n)
        {
            InsertionSort insertionSort = new InsertionSort();
            SelectionSort selectionSort = new SelectionSort();
            ShellSort shellSort = new ShellSort();

            Random random = new Random();

            // 每个元素的主键均为 int 类型,并含有一个 int[20] 值。
            Pair<int, int[]>[] array = new Pair<int, int[]>[n];
            Pair<int, int[]>[] arrayBak = new Pair<int, int[]>[n];
            for (int i = 0; i < n; i++)
            {
                int[] temp = new int[20];
                for (int j = 0; j < 20; j++)
                {
                    temp[j] = random.Next();
                }
                array[i] = new Pair<int, int[]>(random.Next(), temp);
            }
            array.CopyTo(arrayBak, 0);

            double[] results = new double[3];
            results[0] = SortCompare.Time(insertionSort, array);
            arrayBak.CopyTo(array, 0);
            results[1] = SortCompare.Time(selectionSort, array);
            arrayBak.CopyTo(array, 0);
            results[2] = SortCompare.Time(shellSort, array);
            return results;
        }


        /// <summary>
        /// 获取一个随机 <see cref="string"/>。
        /// </summary>
        /// <param name="n"><see cref="string"/> 的长度。</param>
        /// <param name="random">随机数生成器。</param>
        /// <returns>获取一个随机 <see cref="string"/>。</returns>
        static string RandomString(int n, Random random)
        {
            char[] value = new char[n];
            for (int i = 0; i < n; i++)
            {
                value[i] = (char)random.Next(char.MinValue + 10, char.MaxValue - 10);
            }
            return new string(value);
        }
    }
}

写在前边整个项目都托管在了 Github 上: 那风度翩翩节内容只怕会用...

本文由乐虎游戏发布于计算机资讯,转载请注明出处:算法(第四版)C#题解——2.1,

关键词:

WebService入门之CXF教程

import javax.jws.WebService; 相关教程: CXF使用Tomcat发布WebService的简单例子http://www.linuxidc.com/Linux/2011-12/49309.htm (3)将解压...

详细>>

在CentOS上安装rvm

本文系统CentOS6.5 x64 如果是Ubuntu系统,先安装编译环境 Ruby On Rails是一个用Ruby语言写的开源Web框架,和J2EE,PHP等类似...

详细>>

《分布式一致性协议raft简介》

3.2.2. 下面为一个 etcd 集群选举过程的简单描述: ➢ 初始状态下集群中的所有节点都处于 follower 状态。 ➢ 某一时刻...

详细>>

mg电子游戏娱乐场Liunx PHP的GD库 增多 jpeg 文件的援救

GD Support enabled  代码如下 本文永久更新链接地址 :http://www.linuxidc.com/Linux/2014-11/109911.htm 很显然多了个 JPEG Support en...

详细>>