欢迎光临
我的个人博客网站

C#实现——十大排序算法之插入排序


插入排序法

1.工作原理(算法思路)

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

2.动图演示

C#实现——十大排序算法之插入排序

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();      } } 

输出结果:
C#实现——十大排序算法之插入排序

4.性能分析

1)复杂度
C#实现——十大排序算法之插入排序

2)插入排序法特点

  • 在数组元素规模较小的时候,插入排序法的运行效率很高。其经常用在一些其他排序方法中(比如归并排序以及快速排序)来对排序进行优化。
  • 不同于选择排序法,当一个数组几乎有序的时候,插入排序法所需要的时间要比其他的排序法快得多。因此插入排序法的排序时间取决于数组元素的初始顺序,在最好的情况下,插入排序法运行时间能达到线性级别。
赞(0) 打赏
未经允许不得转载:张拓的天空 » C#实现——十大排序算法之插入排序
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏