算法：插入排序（Insertion Sort）

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Threading.Tasks;
 6 
 7 namespace DataStuctureStudy.Sorts
 8 {
 9     /// <summary>
10     /// 将数组分为两部分：已排序部分和未排序部分，对数组执行一次遍历，将遍历中的
11     /// 当前元素插入到已排序的部分。
12     /// 初始状态已排序部分只包括一个元素。
13     /// </summary>
14     class InsertionSort<T>
15         where T : IComparable<T>
16     {
17         private static void Swap(T[] items, int left, int right)
18         {
19             if (left != right)
20             {
21                 var temp = items[left];
22                 items[left] = items[right];
23                 items[right] = temp;
24             }
25         }
26 
27         public static void Sort(T[] items)
28         {
29             for (
30                 var sortedRangeEndIndex = 1;
31                 sortedRangeEndIndex < items.Length;
32                 sortedRangeEndIndex++)
33             {
34                 if (items[sortedRangeEndIndex].CompareTo(items[sortedRangeEndIndex - 1]) < 0)
35                 {
36                     int insertIndex = FindInsertionIndex(items, items[sortedRangeEndIndex]);
37                     Insert(items, sortedRangeEndIndex, insertIndex);
38                 }
39             }
40         }
41 
42         private static int FindInsertionIndex(T[] items, T valueToInsert)
43         {
44             for (var i = 0; i < items.Length; i++)
45             {
46                 if (items[i].CompareTo(valueToInsert) > 0)
47                 {
48                     return i;
49                 }
50             }
51 
52             throw new InvalidOperationException();
53         }
54 
55         private static void Insert(T[] items, int indexInsertingFrom, int indexInsertingAt)
56         {
57             var temp = items[indexInsertingFrom];
58 
59             for (var i = indexInsertingFrom; i > indexInsertingAt; i--)
60             {
61                 items[i] = items[i - 1];
62             }
63 
64             items[indexInsertingAt] = temp;
65         }
66     }
67 }