1 using System;
 2  using System.Collections.Generic;
 3 
 4 namespace Com.Colobu.Algorithm.Insertion
 5 {
 6     /// <summary>
 7     /// 插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。
 8     /// 它的工作原理是通过构建有序序列，对于未排序数据，
 9     /// 在已排序序列中从后向前扫描，找到相应位置并插入。
10     /// 插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），
11     /// 因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，
12     /// 为最新元素提供插入空间。
13     /// 
14     /// 平均时间复杂度:O(n^2)
15     /// Stability:Yes
16     /// </summary>
17     public class InsertionSortAlgorithm
18     {
19         public static void InsertionSort<T>(IList<T> szArray) where T : IComparable
20         {
21             int count = szArray.Count;
22             int j;
23             T temp;
24             for (int i = 1; i < count; i++)
25             {
26                 temp = szArray[i];//store the original sorted array in temp
27                 for (j = i; j > 0 && (temp.CompareTo(szArray[j - 1]) < 0); j--)//compare the new array with temp
28                 {
29                     szArray[j] = szArray[j - 1];//all larger elements are moved one pot to the right
30                 }
31                 szArray[j] = temp;
32             }
33 
34         }
35     }
36 }
37