c++实现排序算法之希尔排序方式

C++实现排序算法之希尔排序

前置知识

• 希尔排序是一种基于插入排序的排序算法
• 插入排序是一种简单直观的排序算法

算法思路

希尔排序是一种分组插入排序的算法。它的基本思想是：先将待排序序列按照一定规则分成若干子序列，对各个子序列进行插入排序，然后逐步缩小子序列的长度，最终使整个序列成为一个有序序列。

例如，对于一个序列 5 2 8 9 1 3 7 6 4，我们可以使用希尔排序的方式对其进行排序。

1. 选择一个增量序列 $t_1, t_2, \cdots, t_k$ 来确定一个间隔序列，例如：$t_1 = 5, t_2 = 3, t_3 = 1$；
2. 按照确定的间隔序列，将序列分成若干子序列，每个子序列使用插入排序算法进行排序；
3. 逐渐缩小间隔序列的大小，重复步骤 2，直到间隔为 $1$ 的时候，整个序列就变成了一个有序序列。

此处代码的实现中采用了最朴素的希尔排序算法。其实现过程分为两个步骤：

1. 计算增量序列，确定间隔序列；
2. 对当前间隔下的子序列进行排序，直到所有元素排序完成。

代码实现

下面给出 C++ 的实现代码。

void ShellSort(vector<int>& nums) {
    int n = nums.size();

    // 计算增量序列
    int gap = n / 2;
    while (gap > 0) {
        for (int i = gap; i < n; ++i) {  // 对当前间隔下的子序列进行排序
            int temp = nums[i];
            int j = i;
            while (j >= gap && nums[j - gap] > temp) {
                nums[j] = nums[j - gap];
                j -= gap;
            }
            nums[j] = temp;
        }
        gap /= 2;  // 缩小间隔
    }
}

示例说明

示例 1

排序前的序列：5 2 8 9 1 3 7 6 4

使用希尔排序进行排序后的序列：1 2 3 4 5 6 7 8 9

示例 2

排序前的序列：9 8 7 6 5 4 3 2 1

使用希尔排序进行排序后的序列：1 2 3 4 5 6 7 8 9

总结

希尔排序相对于其他排序算法，其运行效率在中等规模的数据下表现较好，但在大规模数据下表现一般。

其时间复杂度为：

• 当增量序列为 $t_1 = 1$ 时，时间复杂度为 $O(n^2)$；
• 当增量序列为 $t_1 = n / 2, t_2 = t_1 / 2, \cdots, t_k = 1$ 时，时间复杂度为 $O(n^{3/2})$。

在实际开发中，需要根据数据规模和排序效率需要，选择适当的排序算法。