希尔排序

最近在全面学习数据结构，常用算法记录：希尔排序，基本思想是选定一个增量 $d<n$，将元素按此增量分组（所有相距 $d$ 的元素为一组），然后在各个子序列内进行插入排序，完成后缩小增量 $d'(d'<d)$，如此反复操作，直到增量 $d = 1$ 为止，此时就成了标准的插入排序，但此时大部分元素已经有序，只需要少量操作，甚至不用操作即可完成排序。该排序算法为不稳定排序。

希尔排序还是比较绕的，需要多看看，多画一画。

最坏时间复杂度：$O(n^2)$
$n$ 在某范围内可达：$O(n^{1.3})$
目前无法用数学手段证明确切的时间复杂度。

#include <iostream>

using namespace std;

void shellSort(int arr[], int n);

int main()
{
    int arr[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11};
    int length = (int)(sizeof(arr) / sizeof(int));  //数组长度
    shellSort(arr, length);
    for (int i = 1; i < length; i++)
        cout << arr[i] << " ";
    return 0;
}

void shellSort(int arr[], int n)
{
    int d, i, j;
    //arr[0]为暂存单元
    for (d = n / 2; d > 0; d /= 2)  //d为步长
    {
        for (i = d + 1; i <= n; i++)    //从子表中第二个元素开始
            if(arr[i] < arr[i - d])     //小于子序列前一项
            {
                arr[0] = arr[i];    //暂存待插入元素
                for (j = i - d; j > 0 && arr[0] < arr[j]; j -= d)
                    arr[j + d] = arr[j];    //向后移动，为待插入元素腾出空位
                arr[j + d] = arr[0];    //插入暂存元素
            }
    }
}

版权属于：字节星球/肥柴之家 （转载请联系作者授权）
原文链接：https://www.bytecho.net/archives/2087.html
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。