插入排序

一：插入排序介绍

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的是的位置，以达到排序的目的。

二：插入排序法思想：

​ 插入排序的基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将他插入到有序表中的适当位置，使之成为新的有序表。

三：代码实现

static void Main(string[] args)
       {
           //int[] arr = { 101,34,119,1};
           //insertSort(arr);
           int len = 1000;
           int[] arrs = new int[len];
           for (int i = 0; i < len; i++)
           {
               Random random = new Random();
               int a = (int)random.Next(0, len);
               arrs[i] = a;
               Thread.Sleep(1);
           }
           DateTime date1 = DateTime.Now;
           Console.WriteLine("插入排序前的时间是" + date1.ToString("HH:mm:ss fff"));
           insertSort(arrs);
           DateTime date2 = DateTime.Now;
           TimeSpan time = date2 - date1;
           Console.WriteLine("插入排序后的时间是" + date2.ToString("HH:mm:ss fff"));
           Console.WriteLine("插入排序：{0}个数据所用的时间:{1}", len, time.TotalMilliseconds);
       }
       //插入排序
       public static void insertSort(int[] arr)
       {
           for (int i = 1; i <arr.Length; i++)
           {
               //第一轮：=>{34,101,119,1}
               //定义待插入的数
               int inservalue = arr[i];
               int index = i - 1;//即arr[1]的前面这个数的下标

               //index>=0:保证在inservalue找插入位置，不越界
               //inservalue<arr[index]：待插入的数，还没有找到插入的位置
               //arr[index]后移
               while (index >= 0 && inservalue < arr[index])
               {
                   arr[index + 1] = arr[index];
                   index--;
               }
               //当退出while循环时，说明插入的位置找到index+1
               arr[index + 1] = inservalue;
            //   Console.Write("第{0}轮插入:",i);
             //  print(arr);
           }
       }
       public static void print(int[] arr)
       {
           for (int i = 0; i < arr.Length; i++)
           {
               Console.Write(arr[i]+"\t");
           }
           Console.WriteLine("");
       }

想比较插入和冒泡的执行速度：

四：源码地址

Github拆入排序源码