希尔排序

最近更新于 2023-04-02 00:56

环境

平台工具集：Visual Studio 2022 v143
C 语言标准：C17
字符集：Unicode

算法实现

希尔排序是基于直接插入改进的，将待排序元素按照一定增量分为多个子序列（一般首次增量取总数一半），例如待排序的元素为 9 8 7 6 5 ，共 5 个，增量取 5 / 2 = 2
则先比较下标为 2 和 2-1=0 的两个数，提出 7，和 9 比较，9 大于 7，则 9 移动到 7 的位置，到头了，将提出的 7 插入 9 的位置，得到 7 8 9 6 5
接下来比较 3 和 3 – 1 = 1 …….
……
上面其实就是对每个子序列分别使用直接插入排序
增量下一次取上一次增量的一半 2 / 2 = 1，增量为 1 后，跑完这一轮就代表排序完成。

希尔排序是一种不稳定的排序算法。由于增量的选择是随机的，因此时间复杂度的计算就十分复杂，只是在一定的范围内，但是希尔排序也是第一个时间复杂度突破 O(n^2) 的排序算法
时间复杂度为 nlog_2n，不稳定的排序算法

void insert_sort(int array[], int n, int delta)
{
    for (int i = delta; i < n; ++i)
    {
        if (array[i] < array[i - delta])
        {
            int k, tmp = array[i];
            for (k = i - delta; k >= 0 && tmp < array[k]; k  -= delta)
            {
                array[k + delta] = array[k];
            }
            array[k + delta] = tmp;
            printArray(array, 9);
        }
    }
}

void sort(int array[], int n)
{
    for (int delta = n / 2; delta >= 1; delta /= 2)
    {
        insert_sort(array, n, delta);
    }
}

以 9 8 7 6 5 4 3 2 1 为例，共 n = 9，初始 delta = n / 2 = 4