class InsertSort
{
    public bool Sort(int[] datas)
    {
        if (datas.Length < 1) return false;

        for (int i = 1; i < datas.Length; i++)//默认0为已经有序
        {
            int temp = datas[i];//当前需要插入的元素
            for (int j = 0; j < i; j++)//在有序段中寻找位置
            {
                if (temp < datas[j])//寻找到
                {
                    for (int k = i; k > j; k--)
                    {
                        datas[k] = datas[k - 1];//向后面腾出位置
                    }
                    datas[j] = temp;//坐上宝座
                    break;
                }
            }
        }

        return true;
    }
}

插入排序就是将数组分为了左右两个集合，一个是有序的，一个是无序的，从无序中每次取一个元素，插入到有序的集合中，并保持有序。算法的效率是O(n²)，不适合大量元素的排序。

测试代码：

static void TestInsertSort()
{
    int[] datas = { 5, 6, 9, 1, 100,3, 7, 0, 2, 4 };
    InsertSort insertSort = new InsertSort();
    insertSort.Sort(datas);
    foreach (var data in datas)
    {
        Console.Write(data + " ");//0 1 2 3 4 5 6 7 9 100
    }
}