使用C++实现希尔排序算法

什么是希尔排序？¶

希尔排序（Shell Sort）是插入排序的一种改进版本，也称为“缩小增量排序”。它通过将数组分成多个子序列，对每个子序列进行插入排序，然后逐步缩小增量，直到增量为1时完成整个数组的排序。这种方法的核心思想是让数组中的元素更快地“移动”到正确的位置，从而减少插入排序的移动次数。

希尔排序的基本思路¶

分组：选择一个增量（gap），将数组分成若干个子序列，每个子序列中的元素是相隔gap距离的元素。例如，若数组长度为5，初始增量gap=2，则子序列为[arr[0], arr[2], arr[4]]和[arr[1], arr[3]]。
子序列排序：对每个子序列进行直接插入排序。
缩小增量：将增量gap缩小（通常每次减半，如gap = gap/2），重复步骤1和2，直到gap=1。
最终排序：当gap=1时，整个数组已基本有序，此时只需进行一次完整的插入排序即可完成最终排序。

为什么要缩小增量？¶

初始大增量时，数组被分成较少的子序列，每个子序列较长，插入排序的移动次数少。
随着增量减小，子序列逐渐合并，数组逐渐接近有序，最终只需少量移动即可完成排序。

排序过程示例¶

以数组[12, 34, 54, 2, 3]为例，初始长度n=5，增量gap初始为5/2=2：

第一次分组（gap=2）：
- 子序列1：[12, 54, 3]（索引0,2,4）
- 子序列2：[34, 2]（索引1,3）
- 对每个子序列插入排序后，数组变为[12, 2, 54, 34, 3]。
缩小增量（gap=1）：
- 此时数组已基本有序，直接进行一次插入排序：
- 处理3时，与前面元素54、34、12比较，最终插入到索引0，数组变为[3, 2, 12, 34, 54]。
- 处理2时，与3比较，插入到索引1，数组变为[2, 3, 12, 34, 54]。

最终排序结果：[2, 3, 12, 34, 54]。

C++代码实现¶

#include <iostream>
using namespace std;

// 希尔排序函数
void shellSort(int arr[], int n) {
    // 从大到小设置增量，初始为n/2，每次减半直到gap=0
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个gap分组中的元素进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i]; // 当前待插入的元素
            int j;
            // 从当前元素开始，向前比较并移动元素
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap]; // 元素后移
            }
            arr[j] = temp; // 插入temp到正确位置
        }
    }
}

// 打印数组函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前数组：";
    printArray(arr, n);

    shellSort(arr, n);

    cout << "排序后数组：";
    printArray(arr, n);

    return 0;
}

代码解释¶

外层循环（gap控制）：gap从n/2开始，每次减半，直到gap=0。
中层循环（分组插入排序）：对每个gap，从索引gap开始遍历数组，将每个元素arr[i]视为待插入元素。
内层循环（移动元素）：从i开始向前比较，若前一个元素（arr[j - gap]）大于当前元素（temp），则将前一个元素后移gap位，直到找到插入位置j，最后插入temp。

时间复杂度与空间复杂度¶

时间复杂度：平均为O(n^1.3)（依赖增量选择），最坏为O(n^2)。
空间复杂度：O(1)（仅需临时变量temp）。
稳定性：不稳定（分组插入排序可能改变相等元素的相对顺序）。

总结¶

希尔排序通过分组和缩小增量的方式，有效减少了插入排序的移动次数，在数组较大时比普通插入排序更高效。初学者只需理解“分组→排序→缩小增量→最终排序”的核心逻辑，即可掌握其实现原理。