[算法]插入排序

概念

插入排序就是把数组分为两个区间，一个是有序区间，一个是未排序区间。初始的时候有序区间就只有一个元素，那就是数组的第一个元素，然后取未排序区间中的元素往有序区间中插进去，一直等到未排序区间中的所有元素为空。

int[] t = new int[10] { 54, 23, 43, 2, 3, 5, 1, 2, 6, 7 };
                for (int i = 0; i < t.Length; i++)
                {
                    int v = t[i];
                    int j = i - 1;
                    for (; j > 0; --j)
                    {
                        if (v > t[j])
                        {
                            t[j + 1] = t[j];
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                for(int i = 0; i < t.Length; i++)
                {
                    Console.WriteLine("{0}={1}", i, t[i]);
                }

1. 插入排序算法不需要额外的空间，所以它的空间复杂度为o(1),是原地排序算法。

2. 插入的时候只是插到它所需要的位置，不会修改它后面位置的顺序，所以是稳定排序算法。

3. 最好情况下，我们要排序的数据是有序的，所以我们只需要做o(n)的时间复杂度。最坏的情况下，我们要排序的数据是逆序的，所以我们要做o(nn)的时间复杂度。在数组中插入一个数据的时间平均时间复杂度是o(n)，我们需要执行n次操作，所以平均时间复杂度是o(nn)。