Shell 排序基本信息

Shell 排序 ，也称为递减递增排序，是最古老的排序算法之一，以其发明者 Donald命名。 L. Shell （1959）。它快速，易于理解且易于实施。但是，它的复杂性分析稍微复杂一些。

Shell 排序的想法如下：

1. 将数据序列排列成二维数组
2. 对数组的列进行排序

Shell 排序改进了插入排序。它首先比较相距较远的元素，然后比较相距较远的元素，最后比较相邻元素（实际上是插入排序）。

结果是数据序列被部分排序。重复上述过程，但每次都使用较窄的数组，即列数较少。在最后一步中，数组只包含一列。

Shell 排序示例：

https://i.stack.imgur.com/WTd9p.jpg

Shell 排序的伪代码：

input
foreach element in input
{
    for(i = gap; i < n; i++)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    }
}

辅助空间： O(n) total, O(1) auxiliary
时间复杂度： O(nlogn)