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)