算法系列15天快第3天七经整理[下]

时间：2021-11-14 来源：互联网编辑：宝哥软件园浏览：次

直接插入排序：这种排序其实挺好理解的。一个很现实的例子就是我们打击地主。当我们抓到一手随机牌时，我们必须根据牌的大小来分类。30秒后，扑克整理完毕，4个3 s和5 s，哇.回想一下当时我们是怎么梳理的。最左边的牌是3，第二张牌是5，第三张牌是3。快速插在第一张牌后面，第四张牌是3。我欣喜若狂。快速插在第二张卡后面，第五张卡是3。狂喜，哈哈，一门大炮就是这样产生的。嗯，算法在生活中无处不在，已经融入我们的生活和血液。解释下图：

看着这张图，不知道大家能不能看懂。在插入排序中，数组将分为两种类型，“有序数组块”和“无序数组块”。是的，在第一遍中，从“无序数组块”中提取20作为有序数组块。第二遍，从“无序数组块”中抽取60个数，有序放入“有序数组块”，即20，60。在第三遍中，情况也是如此，但不同的是，10的值比有序数组的值小，因此20，60的位置向后移动，为插入10腾出空间。然后，根据这个规则，所有的插入都可以完成。复制代码如下：使用系统；使用系统。集合。通用；使用系统。Linq使用系统。文字；命名空间InsertSort { public class Program { static void Main(string[]args){ Listint list=new Listint(){ 3，1，2，9，7，8，6 }；控制台。WriteLine('排序前':string。Join('，'，list))；插入排序(列表)；控制台。WriteLine('排序后：')字符串。Join('，'，list))；} static void insert short(list int list){//不需要(int I=1；我列举。计数；I){ var temp=list[I]；int j；//有序序列为(j=I-1；j=0临时列表[j]；j-){ list[j 1]=list[j]；} list[j 1]=temp；} } } } }

Hill排序：看“插入排序”:其实不难发现她有一个缺点：如果当数据为“5，4，3，2，1”时，当我们把“无序块”中的记录插入到“有序块”中时，估计会崩溃，每次插入都要移动位置。这时，插入排序的效率可想而知。根据这个弱点，shell对算法进行了改进，加入了一个叫做“减少增量排序法”的思想，其实挺简单的，但是要注意增量不是随机取的，而是有规律可循的。

首先要明确增量法：第一个增量法是：d=count/2；第二个增量的值是：d=(count/2)/2；直到：d=1；上图观察到的现象是：d=3: 40与50比较时，因为50大，所以不交换。20和30比较，因为30大，不要交换。对比80和60，因为60小，交换。d=2时：40和60比较，不交换，60和30交换。此时兑换后的30比之前的40小，需要用30兑换40，如上图。20和50不交换比较，50和80不交换继续比较。当d=1时：这是前面提到的插入排序，但此时序列几乎是有序的，所以给插入排序带来了很大的性能提升。由于“希尔排序”是“插入排序”的改进版本，让我们比较一下它在1w个数字中的速度。测试如下：按照以下步骤复制代码：使用系统；使用系统。集合。通用；使用系统。Linq使用系统。文字；使用系统。穿线；使用系统。诊断；命名空间shell sort { public class program { static void main(string[]args){//5 comparison for(int I=1；I=5；I){ Listint list=new Listint()；//将1w随机数插入(int j=0；10000j；j ) {螺纹。睡眠(1)；名单。添加(新的随机((整数)日期时间。现在。滴答)。Next(10000，1000000))；} Listint list 2=new Listint()；清单2。AddRange(列表)；控制台。write line(' \ n第“I”个比较：')；秒表手表=新秒表()；看着。start()；插入排序(列表)；看着。stop()；控制台。write line(' \ n插入排序所用的时间：' watch。elapsedmirisseconds)；控制台。WriteLine('输出前十位数字：' string.join('，'，list.take (10))。tolist()))；看着。restart()；ShellSort(列表2)；看着。stop()；控制台。WriteLine('\n花在希尔排序上的时间：' watch。elapsedmirisseconds)；控制台。WriteLine('输出前十位数字：' string.join('，'，list2.take (10)。tolist()))；} }///summary///hill sort////summary///param name=' list '/param static void shell sort(list int list){//取增量int step=list。计数/2；While (step=1) {//不需要(int i=step)的序列；我列举。计数；I){ var temp=list[I]；int j；//有序序列为(j=I-step；j=0临时列表[j]；j=j-step){ list[j step]=list[j]；} list[j step]=temp；}步骤=步骤/2；} }///summary////insert sort/////summary///param name=' list '/param static void insert short(list int list){//不带(int I=1；我列举。计数；I){ var temp=list[I]；int j；//有序序列为(j=I-1；j=0临时列表[j]；j-){ list[j 1]=list[j]；} list[j 1]=temp；}}}}截图如下：。

看的出来，希尔排序优化很多，w级排序，相差70倍哇。合并排序：个人认为我们容易理解的排序基本上是O (n^2)，难理解的排序基本上是N(LogN)，所以合并排序也很难理解，尤其是代码编写，我下午才算出来，嘻嘻。先看图：

归并排序中中两件事情要做：第一： "分", 就是将数组尽可能的分，一直分到原子级别。第二： "并",将原子级别的数两两合并排序，最后产生结果。代码：复制代码代码如下：使用系统；使用系统。集合。通用；使用系统Linq .使用系统。文字；命名空间合并排序{ class Program { static void Main(string[]args){ int[]array={ 3，2，1，8，9，0 }；合并排序(数组，新的int[数组。长度],0,数组。长度-1);控制台WriteLine(字符串Join('，'，array))；}///摘要///数组的划分////summary////param name=' array '待排序数组/param///param name='temparray '临时存放数组/param///param name='left '序列段的开始位置，/param///param name='right '序列段的结束位置/param静态void合并排序(int[]数组，int[] temparray，int left，int right) { if (left right) { //取分割位置int middle=(左/右)/2;//递归划分数组左序列合并排序(数组、温度阵列、左、中);//递归划分数组右序列合并排序(数组，temparray，中间1,右侧);//数组合并操作合并（数组，temparray，左，中间1,右);} }///摘要///数组的两两合并操作////summary////param name=' array '待排序数组/param///param name='temparray '临时数组/param///param name='left '第一个区间段开始位置/param///param name='middle '第二个区间的开始位置/param///param name='right '第二个区间段结束位置/param静态void Merge(int[]数组，int[] temparray，int left，int middle，int right) { //左指针尾int左端=中间-1；//右指针头int rightStart=middle//临时数组的下标int tempIndex=left//数组合并后的长度长度int模板长度=左右1；//先循环两个区间段都没有结束的情况而((左=左端)(右开始=右)){//如果发现有序列大，则将此数放入临时数组if(array[left]array[right start])temparray[tempIndex]=array[left]；else temparray[tempIndex]=数组[右开始]；} //判断左序列是否结束while(left=左端)temparray[TempIndex]=array[left]；//判断右序列是否结束while(右开始=右)temparray[TempIndex]=array[右开始]；//交换数据for(int I=0；我模板；I){ array[right]=temparray[right]；右-;} } }}结果图