排序思想：交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。使数组中任意间隔为h的元素都是有序的。其中h为任意以1结尾的整数序列。
希尔排序的执行时间依赖于增量序列h，好的增量序列的共同特征：
·最后一个增量必须为1；
·应该尽量避免序列中的值（尤其是相邻的值）互为倍数的情况。
排序过程，如图9-43所示：
图9-43 希尔排序
希尔排序比插入排序要快的多，并且数组越大，优势越大。
