C#七大经典排序算法系列（下）

概述今天跟大家聊聊最后三种排序：直接插入排序，希尔排序和归并排序。直接插入排序：

今天跟大家聊聊最后三种排序： 直接插入排序，希尔排序和归并排序。

直接插入排序：

这种排序其实蛮好理解的，很现实的例子就是俺们斗地主，当我们抓到一手乱牌时，我们就要按照大小梳理扑克，30秒后，扑克梳理完毕，4条3，5条s，哇塞...... 回忆一下，俺们当时是怎么梳理的。

最左一张牌是3，第二张牌是5，第三张牌又是3，赶紧插到第一张牌后面去，第四张牌又是3，大喜，赶紧插到第二张后面去，第五张牌又是3，狂喜，哈哈，一门炮就这样产生了。

怎么样，生活中处处都是算法，早已经融入我们的生活和血液。

下面就上图说明：

看这张图不知道大家可否理解了，在插入排序中，数组会被划分为两种，“有序数组块”和“无序数组块”，对的，第一遍的时候从”无序数组块“中提取一个数20作为有序数组块。

第二遍的时候从”无序数组块“中提取一个数60有序的放到”有序数组块中“，也就是20，60。

第三遍的时候同理，不同的是发现10比有序数组的值都小，因此20，60位置后移，腾出一个位置让10插入。

然后按照这种规律就可以全部插入完毕。

using System;using System.Collections.Generic;using System.linq;using System.Text;namespace InsertSort{ public class Program {  static voID Main(string[] args)  {   List<int> List = new List<int>() { 3,1,2,9,7,8,6 };   Console.Writeline("排序前：" + string.Join(",",List));   InsertSort(List);   Console.Writeline("排序后：" + string.Join(",List));  }  static voID InsertSort(List<int> List)  {   //无须序列   for (int i = 1; i < List.Count; i++)   {    var temp = List[i];    int j;    //有序序列    for (j = i - 1; j >= 0 && temp < List[j]; j--)    {     List[j + 1] = List[j];    }    List[j + 1] = temp;   }  } }}

希尔排序：

观察一下”插入排序“：其实不难发现她有个缺点：

如果当数据是”5,4,3,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小，又要将40和30交换，如上图。

              将20跟50比，不交换，继续将50跟80比，不交换。

d=1时：这时就是前面讲的插入排序了，不过此时的序列已经差不多有序了，所以给插入排序带来了很大的性能提高。

既然说“希尔排序”是“插入排序”的改进版，那么我们就要比一下，在1w个数字中，到底能快多少？

下面进行一下测试：

using System;using System.Collections.Generic;using System.linq;using System.Text;using System.Threading;using System.Diagnostics;namespace shellsort{ public class Program {  static voID Main(string[] args)  {   //5次比较   for (int i = 1; i <= 5; i++)   {    List<int> List = new List<int>();    //插入1w个随机数到数组中    for (int j = 0; j < 10000; j++)    {     Thread.Sleep(1);     List.Add(new Random((int)DateTime.Now.Ticks).Next(10000,1000000));    }    List<int> List2 = new List<int>();    List2.AddRange(List);    Console.Writeline("\n第" + i + "次比较：");    Stopwatch watch = new Stopwatch();    watch.Start();    InsertSort(List);    watch.Stop();    Console.Writeline("\n插入排序耗费的时间：" + watch.ElapsedMilliseconds);    Console.Writeline("输出前十个数:" + string.Join(",List.Take(10).ToList()));    watch.Restart();    shellsort(List2);    watch.Stop();    Console.Writeline("\n希尔排序耗费的时间：" + watch.ElapsedMilliseconds);    Console.Writeline("输出前十个数:" + string.Join(",List2.Take(10).ToList()));   }  }  ///<summary>/// 希尔排序///</summary>///<param name="List"></param>  static voID shellsort(List<int> List)  {   //取增量   int step = List.Count / 2;   while (step >= 1)   {    //无须序列    for (int i = step; i < List.Count; i++)    {     var temp = List[i];     int j;     //有序序列     for (j = i - step; j >= 0 && temp < List[j]; j = j - step)     {      List[j + step] = List[j];     }     List[j + step] = temp;    }    step = step / 2;   }  }  ///<summary>/// 插入排序///</summary>///<param name="List"></param>  static voID InsertSort(List<int> List)  {   //无须序列   for (int i = 1; i < List.Count; i++)   {    var temp = List[i];    int j;    //有序序列    for (j = i - 1; j >= 0 && temp < List[j]; j--)    {     List[j + 1] = List[j];    }    List[j + 1] = temp;   }  } }}

截图如下：

看的出来，希尔排序优化了不少，w级别的排序中，相差70几倍哇。

归并排序：

个人感觉，我们能容易看的懂的排序基本上都是O (n^2)，比较难看懂的基本上都是N(LogN)，所以归并排序也是比较难理解的，尤其是在代码

编写上，本人就是搞了一下午才搞出来，嘻嘻。

首先看图：

归并排序中中两件事情要做：

第一： “分”,就是将数组尽可能的分，一直分到原子级别。

第二： “并”，将原子级别的数两两合并排序，最后产生结果。

代码：

using System;using System.Collections.Generic;using System.linq;using System.Text;namespace MergeSort{ class Program {  static voID Main(string[] args)  {   int[] array = { 3,0 };   MergeSort(array,new int[array.Length],array.Length - 1);   Console.Writeline(string.Join(",array));  }  ///<summary>/// 数组的划分///</summary>///<param name="array">待排序数组</param>///<param name="temparray">临时存放数组</param>///<param name="left">序列段的开始位置，</param>///<param name="right">序列段的结束位置</param>  static voID MergeSort(int[] array,int[] temparray,int left,int right)  {   if (left < right)   {    //取分割位置    int mIDdle = (left + right) / 2;    //递归划分数组左序列    MergeSort(array,temparray,left,mIDdle);    //递归划分数组右序列    MergeSort(array,mIDdle + 1,right);    //数组合并 *** 作    Merge(array,right);   }  }  ///<summary>/// 数组的两两合并 *** 作///</summary>///<param name="array">待排序数组</param>///<param name="temparray">临时数组</param>///<param name="left">第一个区间段开始位置</param>///<param name="mIDdle">第二个区间的开始位置</param>///<param name="right">第二个区间段结束位置</param>  static voID Merge(int[] array,int mIDdle,int right)  {   //左指针尾   int leftEnd = mIDdle - 1;   //右指针头   int rightStart = mIDdle;   //临时数组的下标   int tempIndex = left;   //数组合并后的length长度   int tempLength = right - left + 1;   //先循环两个区间段都没有结束的情况   while ((left <= leftEnd) && (rightStart <= right))   {    //如果发现有序列大，则将此数放入临时数组    if (array[left] < array[rightStart])     temparray[tempIndex++] = array[left++];    else     temparray[tempIndex++] = array[rightStart++];   }   //判断左序列是否结束   while (left <= leftEnd)    temparray[tempIndex++] = array[left++];   //判断右序列是否结束   while (rightStart <= right)    temparray[tempIndex++] = array[rightStart++];   //交换数据   for (int i = 0; i < tempLength; i++)   {    array[right] = temparray[right];    right--;   }  } }}

结果图：

ps:

插入排序的时间复杂度为：O(N^2)

希尔排序的时间复杂度为：平均为：O(N^3/2)

最坏：O(N^2)

归并排序时间复杂度为： O(NlogN)

空间复杂度为: O(N)

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持编程小技巧。

总结

以上是内存溢出为你收集整理的C#七大经典排序算法系列（下）全部内容，希望文章能够帮你解决C#七大经典排序算法系列（下）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。