1.直接插入排序
两个数组，有序数组和无序数组。
排序前：无序数组里面所有的值都是无序的，有序数组没有值
排序中：无序数组中拿出一个数，放到有序数组当中，有序数组拿到数，将其按照大小有序的插入到无序数组中
排序后：无序数组中没有数，有序数组中的数为有序的。
假设有一组无序序列 R0, R1, ... , RN-1。
(1) 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。
(2) 然后，我们要依次把 R1, R2, ... , RN-1 插入到这个有序序列中。所以，我们需要一个外部循环，从下标 1 扫描到 N-1 。
(3) 接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。由前面所述，我们可知，插入Ri时，前 i-1 个数肯定已经是有序了。
所以我们需要将Ri 和R0 ~ Ri-1 进行比较，确定要插入的合适位置。这就需要一个内部循环，我们一般是从后往前比较，即从下标 i-1 开始向 0 进行扫描。
代码：
static void InsertSort(List<int> list) { //无序序列 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列 for (int i = 1; i < list.Count; i++) { var temp = list[i]; int j; //有序序列 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位 for (j = i - 1; j >= 0 && temp < list[j]; j--) { list[j + 1] = list[j]; }
list[j + 1] = temp; } }
时间复杂度
当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。
当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N2)。
所以，数据越接近正序，直接插入排序的算法性能越好。
2.希尔(Shell)排序
希尔排序的基本思想是：
把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
static void ShellSort(List<int> list) { //取增量 int step = list.Count / 2; while (step >= 1) { //无序序列 把距离为step的元素编为一个组，扫描所有组 for (int i = step; i < list.Count; i++) { var temp = list[i]; int j; //有序序列 对距离为 step 的元素组进行排序 for (j = i - step; j >= 0 && temp < list[j]; j = j - step) { list[j + step] = list[j]; } list[j + step] = temp; } step = step / 2; // 减小增量 } }
直接插入排序和希尔排序的比较
直接插入排序是稳定的；而希尔排序是不稳定的。
直接插入排序更适合于原始记录基本有序的集合。
希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。
直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。