算法与数据结构(8)：希尔排序

希尔排序是一种更高效的插入排序算法。

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

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

希尔排序的示意如下：

从上图可以希尔排序对元素进行划分时是按索引对增量取模的方式，例如第趟时，对索引按取模可以将元素划分为个区域，然后各个区域分别进行插入排序，然后取下一个增量重复上述过程，直至最后一趟增量为完成后排序算法结束。

可知增量的选择是希尔排序中最重要的部分，假定数组有个元素，可以取初始增量为，并继续以的方式缩小增量。

希尔排序的C++实现如下：

/**
 * 希尔排序
 * 算法复杂度O(n(\text{log}_2 n)^2)
 */
template <class T>
void shell_sort(T *arr, int n)
{
    int gap = n >> 1; // 初始化增量为gap = n / 2
    while (gap > 0)
    {
        // 对不同的分组进行插入排序
        for (int i = gap; i < n; ++i)
        {
            int t = arr[i];
            int j = 0;
            for (j = i - gap; j >= 0 && arr[j] > t; j -= gap)
            {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = t;
        }
        gap >>= 1;
    }
}