插入排序法

1.工作原理（算法思路）

新建一个指针，指针左边的所有元素都是有序的。但是他们的位置并不是最终位置，一个指针从左向右扫描，若指针所在处的元素比左边元素小，则将该元素向前浮动至适当位置，使指针左侧元素仍然保持有序。当指针扫描到整个数组元素的末尾时，数组排序完成。

2.动图演示

3.C#代码实现

根据原理设计算法：

  class Program
{
    //插入排序法
    public static void insertSort(int[] array)
    {
        //for循环：i作为指针，进行从左到右扫描数据的工作
        //指针i从1开始扫描，因为i=0时指针左侧无元素
        for (int i = 1; i < array.Length; i++)
        {
            //temp作为指针键值
            int temp = array[i];

            //新建变量j，从i开始向左扫描已经有序的元素，并与temp比较
            //若temp小于扫描元素，则将j指针元素向右移位腾出空间
            int j = i;
            while (j > 0 && array[j - 1] > temp)
            {
                array[j] = array[j - 1];
                j--;
            }
            //循环完成后将temp放在j指针位置，完成本次插入
            array[j] = temp;
        }

    }

    //打印数组
    public static void printArray(int[] array)
    {
        foreach (int item in array)
        {
            Console.Write(item + "\t");
        }
        Console.WriteLine();
    }

    //主函数入口
    static void Main(string[] args)
    {
        int[] array = new int[10] { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
        printArray(array);
        insertSort(array);
        printArray(array);
        Console.ReadKey();

    }
}

输出结果：

4.性能分析

1）复杂度

2）插入排序法特点

• 在数组元素规模较小的时候，插入排序法的运行效率很高。其经常用在一些其他排序方法中（比如归并排序以及快速排序）来对排序进行优化。
• 不同于选择排序法，当一个数组几乎有序的时候，插入排序法所需要的时间要比其他的排序法快得多。因此插入排序法的排序时间取决于数组元素的初始顺序，在最好的情况下，插入排序法运行时间能达到线性级别。