希尔排序

最近更新于 2024-05-06 07:58

环境

平台工具集：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

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	delta	i	k
9	8	7	6	5	4	3	2	1	4	4	0
5	8	7	6	9	4	3	2	1	5	1
5	4	7	6	9	8	3	2	1	6	2
5	4	3	6	9	8	7	2	1	7	3
5	4	3	2	9	8	7	6	1	8	4
5	4	3	2	8	7	6	9	0
1	4	3	2	5	8	7	6	9	2	2	0
3	1
1	2	3	4	5	8	7	6	9	4	2
0
5	3
1
6	4
6	2
6	0
7	5
1	2	3	4	5	6	7	8	9
…	…	…	…	…	…	…	…	…	…	…	…