希尔排序 是插入排序的一种优化算法，时间复杂度为O(n^3/2)，是一种不稳定的排序算法，其基本流程如下：
在基本的插入排序中，每次比较完之后将操作数往前移动一个单位，有时候可能得需要移动很多次才能到达指定位置，而希尔排序是每轮移动的间隔是改变的，先将整个数组分成几组，然后按组间距移动，一轮完毕后缩小间距，直到最后间距为1，此时变成了插入排序，不过此时数组已经是大部分有序的情况了，所以用插入排序速度会有所提升(一般取初始间隔为数组长度的一半) 开始数组为 ：1, -1, 2, 5, -4, 0, -2, -3, 3, 4 一开始间隔 gap = 10 / 2 = 5 ，即所有间隔为 5 的数组成一个组，所以分组为： 1(1)，-1(2)，2(3)，5(4)，-4(5)，0(1)，-2(2)，-3(3)，3(4)，4(5) 括号内的数字表示这个操作数所在的组号，可以看到当 gap 为数组长度的一半时，此时会有 gap 个组，每个组内的成员是 2 或 3(如果数组长度是奇数，那么第一组会有 3 个成员)个，然后组内的移动方法跟基本插入排序是一致的：
第一轮移动：首先比较第一组： 1(1)，-1(2)，2(3)，5(4)，-4(5)，0(1)，-2(2)，-3(3)，3(4)，4(5)，第一组的 1 与 0 比较，发现 1 > 0，与插入排序移动方法一致(忽略其他组的数)： 1(1)，-1(2)，2(3)，5(4)，-4(5)，1(1)，-2(2)，-3(3)，3(4)，4(5)，这一组数是把 1 往后移动 gap 个单位得到的，然后发现第一组的 0 已经比较到头了，因此直接放到头部： 0(1)，-1(2)，2(3)，5(4)，-4(5)，1(1)，-2(2)，-3(3)，3(4)，4(5) 至此，第一组就比较完了，依次比较后面的 2 3 4 5 组并移动后可得： 0(1)，-1(2)，-3(3)，3(4)，-4(5)，1(1)，-2(2)，2(3)，5(4)，4(5)，第 3 和第 5 组移动了，其余两组并未移动
所以，第一轮移动结束后就得到如下数组： 0(1)，-1(2)，-3(3)，3(4)，-4(5)，1(1)，-2(2)，2(3)，5(4)，4(5) 然后 gap 变为原来的 1//2 后重复操作，gap = gap / 2 = 2，相当于重新分组： 0(1)，-1(2)，-3(1)，3(2)，-4(1)，1(2)，-2(1)，2(2)，5(1)，4(2)
第二轮移动：此时第一组的 0 和 -3 比较，需要移动，则此次移动完成后的数组如下： -3(1)，-1(2)，0(1)，3(2)，-4(1)，1(2)，-2(1)，2(2)，5(1)，4(2) 然后比较第一组的 0 和 -4，还是需要移动： -4(1)，-1(2)，-3(1)，3(2)，0(1)，1(2)，-2(1)，2(2)，5(1)，4(2) 再比较第 1 组的 0 和 -2： -4(1)，-1(2)，-3(1)，3(2)，-2(1)，1(2)，0(1)，2(2)，5(1)，4(2) 再比较 0 和 5，不需移动 此时第一组的所有数据就已经移动完成了，可以看出，如果去掉第 2 组的数据，则只剩 -4(1)，-3(1)，-2(1)，0(1)，5(1)，是一个有序数组了，这就是分组的目的，可以单独的把每一组排好序，最后再在整个基本有序的数组中进行插入排序，因此第二轮排序结束之后的数组如下： -4(1)，-1(2)，-3(1)，1(2)，-2(1)，2(2)，0(1)，3(2)，5(1)，4(2)
然后再将 gap 除以 2 ，gap = gap / 2 = 1，此时就变成了基本的插入排序了，分组如下： -4(1)，-1(1)，-3(1)，1(1)，-2(1)，2(1)，0(1)，3(1)，5(1)，4(1)，相当于所有的数都在同一组 第三轮移动就是插入排序
至此，整个数组就会变得有序了，可以写出升序算法如下：
void shellUpSort(int nums[], int numsSize) { int i, j, tmp, gap; for(gap = numsSize/2; gap > 0; gap /= 2) { for(i = 0; i < numsSize-gap; ++i) { if(nums[i] > nums[i+gap]) { tmp = nums[i+gap]; for(j = i; j>=0 && nums[j]>tmp; j -= gap) { nums[j+gap] = nums[j]; } nums[j+gap] = tmp; } } } }