希尔排序（shell sort）这个排序方法又称为缩小增量排序，是1959年D·L·Shell提出来的。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。
希尔排序算法是有三重循环：
最外层循环 for 语句以增量 delta 变化控制，进行若干趟排序，delta 初值为序列长度 n / 2，以后每趟减半，直至为1。
中间 for 语句进行一趟排序，序列分为 delta 组，每组由相距 delta 远的 n / delta 个元素组成，每组元素分别进行直接插入排序。
最内层循环 for 语句进行一组直接插入排序，将一个元素 keys[i] 插入其中所在的组前面的排序子序列。