排序算法-7---希尔排序

概念

希尔排序（Shellsort），也称递减增量排序算法，是一种典型的插入排序算法，通过对原始序列进行分组进行排序。希尔排序是非稳定排序算法。

解题思路

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

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

希尔排序的基本思想就是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

矩阵的列数取决于步长序列(step sequence)
比如，如果步长序列为{1,5,19,41,109...}.. 就代表依次分成109列、41列、 19列、 5列、1列进行排序
不同的步长序列，执行效率也不同

运行过程

1、选择一个增量序列t1，t2，…，tk，其中对于i>j，有ti>tj，tk=1；（增量因子有多种取法，最简单的是t(i+1) = ti/2）
2、按增量序列个数k，对序列进行k 趟排序；
3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

• 例如：
  希尔本人给出的步长序列是n/2k, 比如n为16时，步长序列是{1, 2, 4, 8}

  
  image

代码

java

public void shell_sort(int[] arr) {
    int gap = 1, i, j, len = arr.length;
    int temp;
    while (gap < len / 3)
        gap = gap * 3 + 1;
    for (; gap > 0; gap /= 3)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}

性能

• 时间复杂度

**希尔排序的执行时间依赖于增量序列。 **
希尔排序耗时的操作有：比较 + 后移赋值。

时间复杂度情况如下：（n指待排序序列长度）

1. 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
2. 最坏情况：O(nlog2n)。
3. 渐进时间复杂度（平均时间复杂度）：O(nlog2n)

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n²)好一些。
希尔算法的性能与所选取的增量（分组长度）序列有很大关系。只对特定的待排序记录序列，可以准确地估算比较次数和移动次数。想要弄清比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。

希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。希尔排序没有快速排序算法快，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
（注：专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。）

• 性能分析（稳定性）

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

备注：希尔排序的时间性能优于直接插入排序

参考文章

经典排序算法（5）——希尔排序算法详解

排序：希尔排序（算法）