算法速成（三）七大经典排序之直接插入排序、希尔排序和归并排序

算法速成（三）七大经典排序之直接插入排序、希尔排序和归并排序2014-04-28直接插入排序：

这种排序其实蛮好理解的，很现实的例子就是俺们斗地主，当我们抓到一手乱牌时，我们就要按照大小梳理扑克，30秒后，

扑克梳理完毕，4条3，5条s，哇塞...... 回忆一下，俺们当时是怎么梳理的。

最左一张牌是3，第二张牌是5，第三张牌又是3，赶紧插到第一张牌后面去，第四张牌又是3，大喜，赶紧插到第二张后面去，

第五张牌又是3，狂喜，哈哈，一门炮就这样产生了。

怎么样，生活中处处都是算法，早已经融入我们的生活和血液。

下面就上图说明：

看这张图不知道大家可否理解了，在插入排序中，数组会被划分为两种，“有序数组块”和“无序数组块”，

对的，第一遍的时候从”无序数组块“中提取一个数20作为有序数组块。

第二遍的时候从”无序数组块“中提取一个数60有序的放到”有序数组块中“，也就是20，60。

第三遍的时候同理，不同的是发现10比有序数组的值都小，因此20，60位置后移，腾出一个位置让10插入。

然后按照这种规律就可以全部插入完毕。

using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace InsertSort{public class Program{static void Main（string[] args）{List<int> list = new List<int>（） { 3, 1, 2, 9, 7, 8, 6 };Console.WriteLine（"排序前：" + string.Join（",", list））;InsertSort（list）;Console.WriteLine（"排序后：" + string.Join（",", list））;}static void InsertSort（List<int> list）{//无须序列for （int i = 1; i < list.Count; i++）{var temp = list[i];int j;//有序序列for （j = i - 1; j >= 0 && temp < list[j]; j--）{list[j + 1] = list[j];}list[j + 1] = temp;}}}}