常用排序算法总结5一一希尔排序

定义

希尔排序（英文：shell sort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

算法步骤

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

• 选择步长
• 按照选择的步长对序列进行排序
• 缩短步长
• 返回步骤二继续排序，直到步长为1

步长序列

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。

Donald Shell最初建议步长选择为n/2并且对步长取半直到步长达到1。虽然这样取可以比O(n^2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。

常见的步长序列

代码实现（java）

/**
 * 希尔排序
 */
public static void shellSort(int[] nums) {
    int gap = 1, i, j, len = nums.length;
    int temp;
    // 选择步长
    while (gap < len / 3) {
        // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
        gap = gap * 3 + 1;
    }
    for (; gap > 0; gap /= 3) {
        for (i = gap; i < len; i++) {
            temp = nums[i];
            for (j = i - gap; j >= 0 && nums[j] > temp; j -= gap) {
                nums[j + gap] = nums[j];
            }
            nums[j + gap] = temp;
        }
    }
}

参考文章

• 希尔排序