使用C++ STL实现希尔排序的实例

希尔排序（Shell Sort），又称缩小增量排序，是一种基于插入排序的高效算法改进版本。它通过将原始数组按照一定增量序列分组，对每组内部进行插入排序，然后逐渐减小增量，直到增量为1，最终完成排序。

在C++中，STL并没有直接提供希尔排序的实现，但我们可以通过自定义函数来实现。下面是一个简单的希尔排序示例：

#include <vector>
#include <cstdlib> // 需要stdlib.h头文件获取rand和 srand

void shellSort(std::vector<int>& arr) {
    int n = arr.size();
    // 增量序列的选择有很多方法，这里使用经典的Hibbard增量序列
    const int gap[] = {10, 5, 3, 1}; // 每次减半并调整值
    for (gap_size_t i = 0; i < sizeof(gap) / sizeof(gap[0]); ++i) {
        for (int j = gap[i] ; j < n ; j++) {
            int temp = arr[j];
            // 对每一组进行插入排序
            for (int k = j; k >= gap[i] && arr[k - gap[i]] > temp; k -= gap[i]) {
                arr[k] = arr[k - gap[i]];
            }
            arr[k] = temp;
        }
    }
}

// 示例：
std::vector<int> vec = {9, 7, 5, 11, 12, 2, 14, 3};
shellSort(vec);
for (const auto& num : vec) {
    std::cout << num << " ";
}