C#排序算法之直接插入排序

1. 直接插入排序，也叫插入排序，是9种经典排序方法中最简单的。
2. 原理：以升序为例，在数组中依次往后选择，将要插入的数据插入到已经排列好的数列中。
3. 思路：在数组中，选取数组中第2个数据与第1个数据比较，如果比第1个数据小，则将第2个数据插入到底1个数据的前面，而将原来的第1个数据移到数组的第2个位置，以此类推。
   以数组[6,5,4,3,2,1]为例：
   第1次：5,6,4,3,2,1 选取数组中第2个数据“5”，插入到前面的队列中；
   第2次：4,5,6,3,2,1 选取数组中第3个数据“4”，插入到前面的队列中；
   第3次：3,4,5,6,2,1 选取数组中第4个数据“3”，插入到前面的队列中；
   第4次：2,3,4,5,6,1 选取数组中第5个数据“2”，插入到前面的队列中；
   第5次：1,2,3,4,5,6 选取数组中第6个数据“1”，插入到前面的队列中；

4.举例：
（1）要排序的数组是：[15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14]。

    //直接插入排序是9种经典排序算法中最简单的
    static void Main(string[] args)
    {
        int[] array = { 15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14 }; //待排序数组
        InsertSort(array,array.Length);

        //控制台遍历输出
        Console.WriteLine("排序后的数列：");
        foreach (int item in array)
            Console.Write(item + " ");
        Console.ReadLine();

    }
    static void InsertSort(int[] array,int length)
    {
        for(int i = 1;i< length;i++)
        {
            int temp = array[i];       //每次先记录下来将要插入的值
            for (int j=0;j<=i;j++)
            {
                if(array[j]> temp)    //在插入过程中找到排序数组中比它大的数据
                {
                    for(int k=i;k>j;k--)
                    {
                        array[k] = array[k - 1];   //找到之后，先保存数列好后面已经排列好的数组，排序的数组后移腾出一个位置
                    }
                    array[j] = temp;    //将插入值放在第1个比它大的数值位置
                    j = i;              //最后，可以将 j=i 结束本次循环
                }
            }
            Console.WriteLine("第{0}次：",i);
            foreach (int item in array)
                Console.Write(item + " ");
            Console.WriteLine();
        }
    }

5.输出结果

第1次：
15 22 35 9 16 33 15 23 68 1 33 25 14
第2次：
15 22 35 9 16 33 15 23 68 1 33 25 14
第3次：
9 15 22 35 16 33 15 23 68 1 33 25 14
第4次：
9 15 16 22 35 33 15 23 68 1 33 25 14
第5次：
9 15 16 22 33 35 15 23 68 1 33 25 14
第6次：
9 15 15 16 22 33 35 23 68 1 33 25 14
第7次：
9 15 15 16 22 23 33 35 68 1 33 25 14
第8次：
9 15 15 16 22 23 33 35 68 1 33 25 14
第9次：
1 9 15 15 16 22 23 33 35 68 33 25 14
第10次：
1 9 15 15 16 22 23 33 33 35 68 25 14
第11次：
1 9 15 15 16 22 23 25 33 33 35 68 14
第12次：
1 9 14 15 15 16 22 23 25 33 33 35 68
排序后的数列：
1 9 14 15 15 16 22 23 25 33 33 35 68