希尔排序

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

Table of Contents

环境

平台工具集: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
希尔排序
Scroll to top