插入排序法

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）插入排序法特点

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