C#算法基础之插入排序

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace ConsolePractice
  8 {
  9     class CArray
 10     {
 11         private int[] arr;
 12         //数组大小
 13         private int upper;
 14         //下标
 15         private int numElements;
 16 
 17         /// <summary>
 18         /// 初始化数组参数
 19         /// </summary>
 20         /// <param name="size"></param>
 21         public CArray(int size)
 22         {
 23             arr = new int[size];
 24             upper = size - 1;
 25             numElements = 0;
 26         }
 27 
 28         /// <summary>
 29         /// 插入方法
 30         /// </summary>
 31         /// <param name="item">存储的数</param>
 32         public void Insert(int item)
 33         {
 34             arr[numElements] = item;
 35             numElements++;
 36         }
 37 
 38         /// <summary>
 39         /// 输出方法
 40         /// </summary>
 41         public void DisplayElements()
 42         {
 43             for (int i = 0; i <= upper; i++)
 44             {
 45                 Console.Write(arr[i] + " ");
 46             }
 47             Console.WriteLine();
 48         }
 49 
 50         /// <summary>
 51         /// 清除数组
 52         /// </summary>
 53         public void Clear()
 54         {
 55             for (int i = 0; i <= upper; i++)
 56             {
 57                 arr[i] = 0;
 58             }
 59             numElements = 0;
 60         }
 61 
 62         /// <summary>
 63         /// 插入排序算法
 64         /// </summary>
 65         public void InsertionSort()
 66         {
 67             int inner, temp;
 68             for (int outer = 1; outer <= upper; outer++)
 69             {
 70                 temp = arr[outer];
 71                 inner = outer;
 72                 //把一个元素取出来逐个跟之前的元素比较。
 73                 //若该元素较小则较大的元素往右移。
 74                 //若该元素较大则结束循环。
 75                 while (inner > 0 && arr[inner - 1] >= temp)
 76                 {
 77                     arr[inner] = arr[inner - 1];
 78                     inner -= 1;
 79                 }
 80                 arr[inner] = temp;
 81                 this.DisplayElements();
 82             }
 83         }
 84     }
 85 
 86     class C_shape
 87     {
 88         static void Main()
 89         {
 90             CArray nums = new CArray(10);
 91             Random rnd = new Random(100);
 92             for (int i = 0; i < 10; i++)
 93             {
 94                 nums.Insert(rnd.Next(0, 100));
 95             }
 96             Console.WriteLine("Before sorting:");
 97             nums.DisplayElements();
 98             Console.WriteLine("During sorting:");
 99             nums.InsertionSort();
100             Console.WriteLine("After sorting:");
101             nums.DisplayElements();
102             Console.ReadKey();
103         }
104     }
105 }

运行结果：

结论：

冒泡排序，选择排序和插入排序的执行效率：

在数据较小时：选择排序和冒泡排序的执行效率相等，而插入排序则比其他两种算法速度的慢一倍。

在数据较大时：执行效率：选择排序>冒泡排序>插入排序，选择排序执行效率最高