【经典算法】第三回：插入排序

1.概述

原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序，杂度为O(n²)。

步骤：遍历从第二个元素开始，比较前面的元素是否大于该元素，大于的话，交换位置。依此类推。

理解：手上有一副牌，要按照从小到大的顺序排序，先把第2张跟第一张进行比较，如果第一张大于第二张就调用。再拿第3张牌跟前面两张进行比较，先比较第二张，如果大于换位置，再比较第一张。再拿第4张牌跟前面3张从右往左进行比较，其它牌依此类推。

2.示例

        //插入排序
        public static void InsertionSort(int[] nums)
        {
            for (int i = 1; i < nums.Length; i++)
            {
                int t = nums[i];
                int j = i;

                while ((j > 0) && (nums[j - 1] > t))
                {
                    nums[j] = nums[j - 1];//交换顺序   
                    --j;
                }

                nums[j] = t;
            }
        }
        // int[] list = new[] { 4, 1, 2, 7, 9, 0, 8 };
        //  Sorter.InsertionSort(list);