数据结构与算法——希尔排序

希尔排序是是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本，通过把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法要点

1. 将一个序列中的数据按一定的步长step划分为n组，对每个组中的数据进行插入排序（值得注意的是，每个组进行插入排序时，不需要遍历每一个组，只需要遍历step后的所有元素，然后与同组内的元素比较并插入即可），
2. 依次增加步长后，执行上述操作
3. 直到步长等于序列长度，即n=1
4. 通常递进关系为组元素长度/2

举例说明

1. 一个序列为 [8,9,1,7,2,3,5,4,6,0]，组长度为10，将其划分为10/2组，步长为5，每组存在2个元素，依次对5组进行插入排序操作
   • 第一组排序完成为 [3,9,1,7,2,8,5,4,6,0]
   • 第二组排序完成为 [3,5,1,7,2,8,9,4,6,0]
   • 第三组排序完成为 [3,5,1,7,2,8,9,4,6,0]
   • 第四组排序完成为 [3,5,1,6,2,8,9,4,7,0]
   • 第五组排序完成为 [3,5,1,6,0,8,9,4,7,2]
2. 第一轮完成后的序列为 [3,5,1,6,0,8,9,4,7,2]，每组长度为5，将其划分为5/2组，步长为2，每组存在5个元素，依次对2组进行插入排序操作
   • 第一组排序完成为 [0,5,1,6,3,8,7,4,9,2]
   • 第二组排序完成为 [0,2,1,4,3,5,7,6,9,8]
3. 第二轮完成后的序列为 [3,5,1,6,0,8,9,4,7,2]，每组长度为2，将其划分为2/2组，步长为1，每组存在1个元素，终止轮序
4. 对最终的序列进行插入排序，得到结果

步骤图示

动图演示

代码示例

package Sort;

public class Sort {
    /**
     * 希尔排序(从小到大排序)
     *
     * @param data int[] 数据
     *
     * @return int[]
     **/
    public int[] shellSort(int[] data)
    {
        //插入排序中所需的带插入的值与键
        int insertionValue;
        int insertionIndex;
        //其中step为步长，也是组的数量
        for (int step = data.length / 2; step > 0; step /= 2) {
            //遍历每一个组中，分别执行插入排序
            for (int i = step; i < data.length; i++) {
                //插入排序
                insertionIndex = i;
                insertionValue = data[insertionIndex];
                if (insertionValue < data[insertionIndex - step]) {
                    while (insertionIndex - step >= 0) {
                        if (insertionValue < data[insertionIndex - step]) {
                            data[insertionIndex] = data[insertionIndex - step];
                        } else {
                            break;
                        }
                        insertionIndex -= step;
                    }
                    data[insertionIndex] = insertionValue;
                }
            }
        }
        return data;
    }
}