关于希尔排序及其增量序列的初步探索

· · 题解

P1177 题目传送门

关于希尔排序及其增量序列的初步探索

引言

众所周知，每一个萌新 \texttt{OIer} 在刚开始接触排序算法时都会首先学习排序三傻：冒泡排序，选择排序和直接插入排序。在这三种时间复杂度为 O(n^2) 的排序中，直接插入排序（以下简称插入排序）的常数极小，在数列基本有序的情况下的速度接近 O(n) 。

这也导致了直接插入排序在利用 \texttt{vector} 中极小常数的 \texttt{insert} 时甚至可以以 \texttt{414ms} 的成绩 \texttt{A} 了此题。

而一些其他的更好的排序算法也是由这三种排序算法优化而来，比如快速排序是冒泡排序的优化，而堆排序是选择排序的优化。

而接下来讲的希尔排序则是直接插入排序的优化。作为排序算法史上第一个突破 O(n^2) 时间复杂度的排序算法，它有着极其玄学的时间复杂度和在小规模数组中相当高的速度。

考虑直接插入排序的特点，其

希尔排序就是根据这两项特点做出了改进。

关于希尔排序

希尔排序（英语：\texttt{Shellsort} ），也称递减增量排序算法，是插入排序的一种更高效的改进版本。其名称来自于其提出者随蝴蝶一起消散吧 \texttt{Donald Shell} ，该算法于 \texttt{1959} 年公布，是第一个突破 O(n^2) 时间复杂度的排序算法。

希尔排序通过以下几个步骤来提升插入排序的性能。

  1. 首先，将数列按照一定的增量或梯度或步长（随便怎么叫）分割成一定的子序列。
  2. 对每一个子序列进行直接插入排序。
  3. 缩减增量并回到步骤 1 直到增量为 1（即对整个数组作为一个子序列进行直接插入排序）

这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的增量进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

假设有一个很小的数据在一个升序数列的末端。如果用复杂度为 O(n^2) 的排序（冒泡排序或插入排序），可能会进行 n 次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。

大白话：让需要大幅度移动的数据飞起来快速向前移动(克服特点 2)让数列变得大体有序（满足特点 1）从而加快直接插入排序。

稳定性

在每一次插入排序中，数据是稳定的。但是，相同的数据可能会在各自的插入排序中移动，导致其稳定性被打乱。

增量序列

由以上步骤我们可以得知，我们的增量需要逐步变小，而理论上，任何一个以 1 结束（或者我们把它倒过来说以 1 起始）的增量序列都是可以的。然而，增量序列的选择直接影响了希尔排序的效率，那么，如何选择一个好的增量序列就是一个必须考虑的问题。

\texttt{Shell} 增量序列 \texttt{(1959)}

ps：我们很容易想到，一个好的增量序列中的数大概应该是两两互质的，因为这样每次的子序列都是不同的，有利于数据快速向前移动。

pps：不知道从什么时候开始，增量序列变成由 1 起始了

\texttt{Hibbard} 增量序列 \texttt{(1963)}

\texttt{Knuth} 增量序列 \texttt{(1970)}

\texttt{Sedgewick} 增量序列 \texttt{(1982)}

\texttt{Ciura} 增量序列 \texttt{(2001)}

etc.

后记

这时候就有小天才会问了，哎你这时间复杂度还没证呢。实际上，希尔排序的时间复杂度很多都是猜想反正我不会证，会证的小天才可以分享一下()。

这时候又有小天才会问了，哎比如当 n=1000 时，这 n^\frac 7 6 < n\log n ，那是不是希尔排序会更快呢？

很显然不是这样的，因为 基于比较的排序算法的时间复杂度下界是 O(n\log n)，会证的小天才自己去证一下吧~ 这个真能证。

代码

给出使用 \texttt{Sedgewick} 增量序列的代码，经过实测，使用 \texttt{Ciura} 增量序列的代码比此代码快 \texttt{1ms}。

#include<bits/stdc++.h>
using namespace std;
class P1177
{
public:
    class _MyIn
    {
    public:
        using _I=uint32_t;
        static constexpr bool sign=0;
        #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,BZ,stdin),p1==p2)?EOF:*p1++)
        #ifdef getchar
        static constexpr int BZ=1<<20;
        char buf[BZ],*p1=buf,*p2=buf;
        #endif
        _I operator()()
        {
            _I n=0;
            bool b=0;
            char c=getchar();
            while(c<48||c>57)((sign&&c=='-')?b=1:0),c=getchar();
            while(c>=48&&c<=57)
                n=(n<<1)+(n<<3)+(c^48),c=getchar();
            return b?-n:n;
        }
        _MyIn& operator>>(_I &n){return n=operator()(),(*this);}
        #undef getchar
    }read;
    class _SHELL_SORT
    {
        uint32_t a[16];
    public:
        constexpr _SHELL_SORT():a()///Sedgewick_init
        {
            for(int p=0,i=0;i<16;++p)
                a[i++]=9*(1<<(p<<1))-9*(1<<p)+1,
                a[i++]=(1<<(p+2))*((1<<(p+2))-3)+1;
        }
        template<class T,class F>
        int operator()(T p1,T p2,F cmp)
        {
            for(int tp=upper_bound(a,a+15,p2-p1)-a-1;tp>=0;--tp)
                for(int i=a[tp],tmp=a[tp];p1+i<p2;++i)
                    for(int j=i;j>=tmp&&cmp(*(p1+j),*(p1+j-tmp));j-=tmp)
                        swap(*(p1+j),*(p1+j-tmp));
            return 0;
        }
    }shell_sort;
    uint32_t arr[100010],n;
    P1177()
    {
        n=read();
        for(int i=1;i<=n;++i)
            arr[i]=read();
        shell_sort(arr+1,arr+n+1,less<int>());
        for(int i=1;i<=n;++i)
            printf("%u ",arr[i]);
    }
}obj;
int main()
{
    return 0;
}

本段代码测速 \texttt{55ms}。

完结撒花✿✿ヽ(°▽°)ノ✿✿

了吗？

基于比较的排序算法的时间复杂度下界的证明

真·完结撒花✿✿ヽ(°▽°)ノ✿✿