插入排序一个比较耗时的地方在于需要将元素反复后移，因为它是以1为增量进行比较的元素的后移可能会进行多次。一个长度为n的序列，以1为增量就是一个序列，以2为增量就形成两个序列，以i为增量就形成i个序列。
希尔排序可以被认为是简单插入排序的一种改进，希尔排序的思想是，先以一个较大的增量，将序列分成几个子序列，将这几个子序列分别排序后，合并，在缩小增量进行同样的操作，直到增量为1时，序列已经基本有序，这是进行简单插入排序的效率就会较高。
/// <summary> /// 希尔排序 /// </summary> /// <param name="array">要进行排序的数组</param> /// <param name="n">需要拆分成几组数</param> public void ShellSort(int[] array,int n) { for (int step = n / 2; step > 0; step /= 2) { for (int i = step; i < n; ++i) { int j, value = array[i]; for (j = n - step; j >= 0 && array[j] > value; j -= step) { array[j + step] = array[j]; } array[j + 1] = value; } } }
说实话本人不是很喜欢插入排序这种方式，因为涉及到数组的移动，所以也没有深究，重要的是了解思路。
原文：https://www.cnblogs.com/zangjiapei/p/11436530.html