从0开始学习C++ 第三十二课 希尔排序

希尔排序 (Shell Sort)

概念：
希尔排序（也称递减增量排序算法），是插入排序的一种更高效的改进版本。它通过将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，来改进插入排序的性能。

逐步分析：

1. 选择一个增量序列 t1, t2, ..., tk，其中 ti > tj，tk = 1。
2. 按增量序列个数 k，对序列进行 k 轮排序。
3. 每轮排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

C++ 代码示例：

#include <vector>

// 希尔排序函数
void shellSort(std::vector<int> &nums) {
    int n = nums.size();
    // 初始步长
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 从第 gap 个元素，逐个对其所在组进行直接插入排序操作
        for (int i = gap; i < n; i++) {
            int temp = nums[i];
            int j;
            for (j = i; j >= gap && nums[j - gap] > temp; j -= gap) {
                nums[j] = nums[j - gap];
            }
            nums[j] = temp;
        }
    }
}

代码注释：

• gap 是增量，每次都减少一半，直到减少到 1。
• 外层循环逐步减小 gap，直到 1 为止。
• 内层循环对每个子序列进行插入排序。

时间复杂度：

• 最好情况：O(nlogn)
• 最坏情况：O(n^2)，但是这取决于增量的选择。
• 平均情况：取决于增量序列，但一般认为是 O(n^1.3)。

空间复杂度： O(1)，因为排序是在原地进行的。

是否稳定： 否，希尔排序是不稳定的排序算法。由于最终一次排序时，增量为 1，这实质上是一个插入排序，但由于之前的步骤可能已经改变了相等元素的初始顺序，因此希尔排序不是稳定的。