插入排序是假设一一个数组中的前一段(或者后一段)已经排好序,而将剩下的元素分别插入到合适的位置上,以达到排序目的的一种算法
以下是实现代码,对红色部分有不同的实现方法:

1.         /// <summary>
   
2.         /// 插入排序
   
3.         /// </summary>
   
4.         /// <param name="arr">要排序的数组</param>
   
5.         static void InsertSort1( ref int[] arr)
   
6.         {
   
7.             int keyValue = 0;
   
8.             int pos = 0;
   
9.             for (int key = 1; key < arr.Length;key++ )
   
10.             {
    
11.                 keyValue = arr[key];
    
12.                 pos = key - 1;
    
13.                                while (pos >= 0 && arr[pos] > keyValue)
    
14.                 {
    
15.                     arr[pos + 1] = arr[pos];
    
16.                     pos--;  
    
17.                 }
    
18.                 arr[pos + 1] = keyValue;
    
19.             }
    
20. 
    
21.         }
    
22.         /// <summary>
    
23.         /// 插入排序
    
24.         /// </summary>
    
25.         /// <param name="arr">要排序的数组</param>
    
26.         static void InsertSort2(ref int[] arr)
    
27.         {
    
28.             int key;
    
29.             for (int i = 1; i < arr.Length;i++ )
    
30.             {
    
31.                 key = i - 1;
    
32.                 while(key >=0 && arr[key] > arr[key+1])
    
33.                 {
    
34.                     Swap(ref arr[key], ref arr[key + 1]);
    
35.                     key --;
    
36.                 }
    
37.             }
    
38.         }
    
39.         /// <summary>
    
40.         /// 交换两个数的值
    
41.         /// </summary>
    
42.         /// <param name="i">左值</param>
    
43.         /// <param name="j">右值</param>
    
44.         static void Swap(ref int i,ref int j)
    
45.         {
    
46.             int temp = i;
    
47.             i = j;
    
48.             j = temp;
    
49.         }

复制代码

插入排序采用的是减治法,关于减治法的概念可以百度一下(哈哈,偷懒了)
关于其他算法请参考这里

受教了,谢谢分享

值得学习ing!