一、插入排序（INSERTION-SORT）（设按升序排列）
思路
类比思想：假设桌上有一叠反面朝上的扑克，一个人左手为空，每次右手从这叠扑克的最上边拿一张扑克放到左手。在将扑克插入左手时，都与之前插入的扑克比较大小，插入适当位置，使之按升序排列。当将最后一张牌插入的时候，这叠扑克升序排序结束，得到升序序列。
伪代码描述：A 为待排序数组。
for j = 2 to A.length
key = A[j]
i = j – 1
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i – 1
A[i + 1] = key
C# 代码
static void InsertionSort<T>(T[] arr) where T: IComparable<T>
{
int i, j;
T tmp;
for (i = 1; i < arr.Length; i++)
{
tmp = arr[i];
j = i – 1;
while (j >= 0 && tmp.CompareTo(arr[j]) < 0 ) //tmp < arr[j]
{
arr[j + 1] = arr[j];
j–;
}
arr[j + 1] = tmp;
}
}