数据结构与算法系列文章：数据结构与算法目录
算法步骤：
1、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；
2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
实现：
/// <summary>
/// 插入排序
/// </summary>
/// <param name="arr"></param>
public void InsertSort(int[] arr)
{
int len = arr.Length;
for (int i = 1; i < len; i++)
{
int temp = arr[i];
// 在已经排序好的元素中，从后往前比较
for (int j = i - 1; j >= 0; j--)
{
if (arr[j] > temp)
{
// 交换元素
arr[j + 1] = arr[j];
arr[j] = temp;
}
else
{
// 有序元素未比较的元素中，没有比此元素大的了
break;
}
}
}
}
从代码里我们可以看出，如果找到了合适的位置，就不会再进行比较了，就好比牌堆里抽出的一张牌本身就比我手里的牌都小，那么我只需要直接放在末尾就行了，不用一个一个去移动数据腾出位置插入到中间。
