【排序算法】希尔排序

1.希尔排序的定义

希尔排序（缩小增量排序），是对直接插入排序算法的优化和升级。

2.希尔排序的原理

将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，

对各个子序列分别进行直接插入排序，待整个待排序列“基本有序”后，

对所有元素进行一次直接插入排序。

因此，采用跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

3.希尔排序的流程

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。

随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据成为一组，构成一组有序记录，则完成排序。

实例：

分析：

初始时，有一个大小为 10 的无序序列。

第一趟排序中，设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。

按照直接插入排序的方法对每个组进行排序。

第二趟排序中，把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。

按照直接插入排序的方法对每个组进行排序。

第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。

按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

注：图中两个相等的元素 5 。在排序过程中，两个元素位置交换了。所以，希尔排序是不稳定的算法。

4.希尔排序的代码实现

public class ShellSort { public static int count = 0; public static void main(String[] args) { int[] data = {5, 3, 6, 2, 1, 9, 4, 8, 7}; System.out.println("排序前："); print(data); shellSort(data); System.out.println("排序后： "); print(data); } public static void shellSort(int[] data) { // 计算出最大的h值 int h = 1; while (h <= data.length / 3) { h = h * 3 + 1; } while (h >= 1) { for (int i = h; i < data.length; i += h) { if (data[i] < data[i - h]) { int tmp = data[i]; int j = i - h; while (j >= 0 && data[j] > tmp) { data[j + h] = data[j]; j -= h; } data[j + h] = tmp; } } // print(data); // 计算出下一个h值 h = h / 3; } } public static void print(int[] data) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + "\t"); } System.out.println(); } }

输出结果

排序前： 5 3 6 2 1 9 4 8 7 排序后： 1 2 3 4 5 6 7 8 9

注：常用的h序列由Knuth提出，该序列从1开始，通过公式h = 3 * h +1产生。

5.算法分析

（1）希尔排序的算法性能

（2）时间复杂度

不确定，与步长有关。平均为O(nlogn)

（3）算法稳定性

一次插入排序是稳定的，不会改变相同元素的相对顺序，由于希尔排序的多次插入排序，在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱（见上图），所以是不稳定的。

6.直接插入排序和希尔排序的比较

直接插入排序是稳定的；而希尔排序是不稳定的。

直接插入排序更适合于原始记录基本有序的集合。

希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。

在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。

直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。

本人才疏学浅，若有错，请指出 谢谢！