介绍

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

背景

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

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

基本思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt = 1 (dt < dt-1 … <d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

python

def shell(arr):
    '''
    希尔排序
    '''
    n = len(arr)
    h = 1
    while h < n / 3:
        h = 3 * h + 1
    while h >= 1:
        for i in range(h, n):
            j = i
            while j >= h and arr[j] < arr[j - h]:
                arr[j], arr[j-h] = arr[j-h], arr[j]
                j -= h
        h = h // 3
    print arr

lst = [3, 2, 5, 7, 6, 1, 9, 0, 8, 4]
shell(lst)

Java

public static <AnyType extends Comparable<? super AnyType>> void shellsort(AnyType[] a) {
  int j;
  for(int gap = a.length / 2; gap > 0; gap /= 2)
    for(int i = gap; i < a.length; i++) {
      AnyType tmp = a[I];
      for(j = i; j >= gap && tmp.compareTo(a[j - gap]) < 0; j -= gap)
        a[j] = a[j - gap];
     a[j] = tmp;
    }
}