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     /// 
10     /// 将数组分为两部分：已排序部分和未排序部分，对数组执行一次遍历，将遍历中的11     /// 当前元素插入到已排序的部分。12     /// 初始状态已排序部分只包括一个元素。13     /// 
14     class InsertionSort
     
      15         where T : IComparable
      
       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 }