希尔排序

1. 简介

希尔排序又称缩小增量排序，其也属于插入排序类算法。相较于一般的插入算法、折半插入算法、2-路插入算法以及表插入算法，希尔排序在时间效率上更加优秀。

2. 思想

对于普通的插入算法，其时间复杂度为 $O(n^2)$，且在序列有序时，可以达到最好的时间复杂度 $O(n)$；而且当 $n$ 较小时，由于移动的元素较少，插入排序效率也比较高。

因此，我们可以采用分治的思想，先将整个待排序序列分割成为若干个子序列分别进行插入排序，待整个序列「基本有序」时再对全体进行插入排序，即自底向上实现整个序列的排序。

【注】这里的子序列不是简单的逐段分割，而是将相隔某个增量的元素组成一个子序列，这样对子序列进行插入排序时，元素就不是一步一步移动，而是跳跃式地往前移。

3. 伪代码

ShellSort(A, D) {
    // 按增量序列 D 对数组 A 进行希尔排序
    for i = 1 to D.length
        //  以下类比与一般的插入排序，增量为 D[i] 而不是 1 
        for j = D[i] + 1 to A.length
            key = A[j]
            k = j - D[i]
            while k > 0 and A[k] > key
                A[k+D[i]] = A[k]
                k = k - D[i]
            A[k+D[i]] = key
}

其中，数组 D 为增量序列。常用的增量序列有：

• $D[k] = 2 \lfloor {n \over 2^{k+1}} \rfloor + 1 , \ \ 0 \lt k \leq t = \lfloor \log_2 n \rfloor$
  希尔排序时间复杂度 $O(n^{1.5})$ 。

• $D[k] = 2^{t - k} - 1 , \ \ 0 \leq k \lt t = \lfloor \log_2 (n+1) \rfloor$
  希尔排序时间复杂度 $O(n^{1.5})$ 。

• $D[k] = \lfloor 2^{t - k} + 1 \rfloor, \ \ 0 \leq k \leq t+1, \ \ t = \lfloor \log_2 (n-1) \rfloor$
  希尔排序时间复杂度 $O(n^{1.5})$ 。

• $D[k] = \lfloor {3^{t - k} - 1 \over 2} \rfloor, \ \ 0 \leq k \lt t = \lfloor \log_3 (2n+1) \rfloor$
  希尔排序时间复杂度 $O(n^{1.5})$ 。

• $D[k] = \lfloor {3^{t - k} - 1 \over 2} \rfloor, \ \ 0 \leq k \lt t = \lfloor \log_3 (2n+1) \rfloor$
  希尔排序时间复杂度 $O(n^{1.5})$ 。

• $D[k] = \begin{cases} 1, & \ \ k = t \\ 4^{t-k} + 3 \cdot 2^{t-k-1} + 1, & \ \ 0 \leq k \lt t \\ \end{cases} , \ \ t = \lfloor \log_2 (\sqrt{9+16(n-1)} - 3) - 2 \rfloor$
  希尔排序时间复杂度 $O(n^{4 \over 3})$ 。

• $D[k] = 2^i 3^j, \ \ 0 \lt 2^i 3^j \leq n$，$i,j$ 递减到 0（即连续递减到 1 的光滑数 $2^p 3^q$）
  希尔排序时间复杂度 $O(n \log^2 n)$ 。

希尔排序是不稳定的、原址的。不稳定原因在于希尔排序中不同段交换元素时会打乱相等元素初始的相对位置。

4. 模板

#include <bits/stdc++.h>
using namespace std;

#ifndef _SHELLSORT_
#define _SHELLSORT_
#define ll int

// 比较元素
template < typename T >
bool compare(const T & a, const T & b)  { return a < b; }
// 希尔排序

template < typename T >
void shellSort(T *bA, T *eA, ll *bD, ll *eD, bool (*cmp)(const T & a, const T & b) = compare) {
    ll len_A = eA - bA;
    ll len_D = eD - bD;
    T *A = bA;
    ll *D = bD;
    // 按增量序列 D 对数组 A 进行希尔排序
    for(ll i = 0; i < len_D; ++i) {
        //  以下类比与一般的插入排序，增量为 D[i] 而不是 1 
        for(ll j = D[i]; j < len_A; ++j) {
            T key = A[j];
            ll k = j - D[i];
            while(~k && compare(key, A[k])) {
                A[k+D[i]] = A[k];
                k = k - D[i];
            }
            A[k+D[i]] = key;
        }
    }
}
#endif