希尔排序

希尔排序是一种逐步调整，让整个数组越来越有序，最终完全排序的算法。

和桶排序的思想比较接近，也是先分组，然后组内嵌套调用其他排序算法

希尔排序是根据间隔d，把间隔为d的元素都划分到一个组内，即根据下标mod d的同余系进行分组，组内调用其他排序算法。

刚开始d很大，然后逐渐减小，最后一次d=1，因为d=1的时候调用了其他排序算法，所以肯定是完成了排序任务的。

常见排序算法：https://blog.csdn.net/nameofcsdn/article/details/113362124

按照希尔排序的步骤，很容易就产生一个疑问，既然希尔排序的最后一趟就是一次完整的简单排序，那希尔排序相对于简单排序而言还有什么优势呢？

Shell sort can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort)

如果是内嵌插入排序，主要好处是时间复杂度可能是低于插入排序的（取决于间隔序列）。

如果是内嵌冒泡排序，主要好处是比冒泡本身的交换次数少一些。

代码实现：

template
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
    vector vd = getd(len); //获取间隔序列
    for (auto d:vd) {
        Sort(arr, len, d, cmp); //间隔式排序
    }
}

希尔排序框架的代码是固定的，所以下面还需要讨论的是：

（1）内嵌排序

void Sort(int* arr, int len, int d, bool(*cmp)(T a, T b)) //间隔式排序

要么是插入排序，要么是冒泡排序

（2）获取间隔序列

vector getd(int len)

获取一个递减的间隔序列，最后一个一定是1

当我们描述希尔排序的间隔序列时，既可以递增描述，如1,2,4,8，也可以递减描述，8,4,2,1，因为希尔排序的步骤是明确是，一定是按照递减的间隔序列依次调用内嵌排序。所以关于这个描述，下文不再专门解释。

内嵌冒泡排序的希尔排序有排序网络， 以8个元素为例，如果采用原始序列d=4,2,1，那么排序网络如下：

 PS：

如果n=8，那么采用原始的d=4,2,1这个序列是很不明智的选择，因为效率低。

template
void Sort(int* arr, int len, int d, bool(*cmp)(T a, T b))  //间隔式冒泡排序
{
    for (int s = 0; s < d; s++) {
        for (int i = len - d; i > 0; i -= d) {
            for (int j = s; j < i; j += d) {
                if (cmp(arr[j + d], arr[j]))exchange(arr + j + d, arr + j);
            }
        }
    }
}

以1000个随机数的排序为例，冒泡排序的交换次数是257362

以500 250 125 62 31 15 7 3 1作为间隔序列，内嵌冒泡排序的希尔排序的总交换次数为7256

由此可见，内嵌冒泡的希尔排序比冒泡本身的交换次数明显要少。

PS:

我测试了一些，内嵌插入排序的希尔排序，交换次数和内嵌冒泡的希尔排序是一样的。

内嵌插入排序的一般不是遗忘比较算法，没有排序网络。

template
void Sort(int* arr, int len, int d, bool(*cmp)(T a, T b))  //间隔式插入排序
{
    for (int s = 0; s < d; s++) {
        for (int i = s + d; i < len; i += d) {
            for (int j = i; j > s; j -= d) {
                if (cmp(arr[j], arr[j - d]))exchange(arr + j, arr + j - d);
                else break;
            }
        }
    }
}

希尔排序的时间复杂度和间隔序列关系很大，所以有很多常用的间隔序列被发明出来。

一般来说，间隔序列都是无穷序列，和数列规模无关。

而对于一个特定的数列规模n和间隔序列A，一般都是把A中所有小于n的数取出来，作为这个特定问题的间隔序列。

下文不再赘述，只讨论无穷序列。

d的取值方式其实并不严格限制，只要是逐渐减小，最后取到1即可。

时间复杂度：

简单的分析来看，最坏时间复杂度是O（n^2），

但是精确分析的话还能提出各种更严格的渐进上确界，而且和间隔d的取值序列有关，比较复杂，至今仍然没有很好的解答。

五，

 但是对于2^p*3^q增量的希尔排序，采用插入排序，每一趟排序中的每个数只需要与前面的数比较一次（插入就会停止），所以这个特定的希尔排序也可以用排序网络描述：