希尔排序（Shell Sort）

希尔排序是插入排序的一个改进版本。希尔排序的改进基础在于插入排序具有对接近正序（partially sorted）的序列能高效进行排序的特性，通过对精心选择的部分元素进行排序，让整个序列趋近于正序，最终完成排序。

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

希尔排序的核心思想是利用插入排序在少量数据（大步长）和接近正序（小步长）有更高效率的特点，通过选择合适的步长序列，从而提高整体的效率。

希尔排序算法的运作如下：

1. 将要进行排序的元素根据步长（M）划分成M个区域，每个区域包括前M个元素中的一个元素及其依次相距为M的其他元素。
2. 对每个区域进行插入排序
3. 缩小步长M，重复上面的运算，直到M为1.

Shell Sort (Source: wikipedia)

C#代码

void ShellSort<T>(T[] arr) where T : IComparable<T>{
    int len = arr.length;
    int number = len / 2;
    while (number >= 1) {
        for (int i = number; i < len; i++) {
            temp = array[i];
            int j = i - number;
            while (j >= 0 && arr[j].CompareTo(temp) > 0) {
                arr[j + number] = arr[j];
                j = j - number;
            }
            arr[j + number] = temp;
        }
        number = number / 2;
    }
}

正确性分析

当步长为1时，算法变为普通插入排序，这保证了数据一定会被排序。

时间与空间复杂度

希尔排序的时间复杂度与选择的步长有关，比较难以分析（out of scope），但是总体来说，选择适当的步长，最差情况会优于插入排序的O(N^2). 但依然比O(NlogN)要差。

其它特性

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。

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

相关问题

回到算法页