C++ 希尔排序（Shell Sort）优化版 - 介绍与可视化演示

#include 
#include 
#include 
#include 
#include  // 需要 std::reverse, std::sort, std::unique, std::pow
#include   // 可选, 用于 std::iota 生成测试数据

/**
 * @brief 生成希尔排序所需的增量序列 (gap sequence)。
 * @param n 数组的大小。
 * @param sequenceType 增量序列的类型 ("shell", "hibbard", "knuth", "sedgewick")。
 * @return 一个包含增量值的整数向量，按降序排列。
 */
std::vector generateGaps(int n, const std::string& sequenceType) {
    std::vector gaps;

    if (sequenceType == "shell") {
        // Shell 原始序列: N/2, N/4, ..., 1
        for (int gap = n / 2; gap > 0; gap /= 2) {
            gaps.push_back(gap);
        }
    }
    else if (sequenceType == "hibbard") {
        // Hibbard 序列: ..., 15, 7, 3, 1 (2^k - 1)
        int k = 1;
        int gap = (1 << k) - 1; // 计算 2^k - 1
        while (gap < n) { // 生成所有小于 n 的 Hibbard 数
            gaps.push_back(gap);
            k++;
            gap = (1 << k) - 1;
        }
        std::reverse(gaps.begin(), gaps.end()); // 按降序使用
    }
    else if (sequenceType == "knuth") {
        // Knuth 序列: ..., 40, 13, 4, 1 ((3^k - 1) / 2)
        int k = 1;
        int gap = 1;
        // 产生序列直到 gap >= n/3 (一个常用的停止条件)
        while (gap < n / 3) {
             gaps.push_back(gap);
             k++;
             gap = (std::pow(3, k) - 1) / 2;
        }
         std::reverse(gaps.begin(), gaps.end()); // 按降序使用
         // 如果生成的序列为空 (n <= 3) 或第一个 gap 就大于等于 n, 则至少需要 gap=1
         if (gaps.empty() || (gaps.size() == 1 && gaps[0] >= n)) {
             gaps.clear();
             gaps.push_back(1);
         } else if (gaps.back() != 1 && n > 1) {
             // 确保序列包含 1, 除非 n=1
             bool foundOne = false;
             for(int g : gaps) if(g == 1) foundOne = true;
             if(!foundOne) gaps.push_back(1);
         }
    }
    else if (sequenceType == "sedgewick") {
        // Sedgewick 序列 (使用两种形式生成: 4^k + 3*2^(k-1) + 1 和 9*(4^k - 2^k) + 1)
        std::vector sedGaps; // 使用 long long 防止溢出
        int k = 0;
        while (true) {
            long long gap1 = 0, gap2 = 0;
            if (k == 0) {
                gap2 = 1; // k=0 时, 第二个公式产生 1
            } else {
                // 公式 1: 4^(k) + 3 * 2^(k-1) + 1 (原实现 k+1 和 k 可能有误, 这里修正为 k 和 k-1)
                 // 或者更常见的形式: 4^i + 3*2^(i-1) + 1 for i >= 1. Let's use this.
                 double p1 = std::pow(4.0, k) + 3.0 * std::pow(2.0, k - 1) + 1.0;
                 gap1 = static_cast(p1);

                 // 公式 2: 9*(4^k - 2^k) + 1 for k >= 0.
                 double p2 = 9.0 * (std::pow(4.0, k) - std::pow(2.0, k)) + 1.0;
                 gap2 = static_cast(p2);
            }

            bool added = false;
            if (gap1 > 0 && gap1 < n) {
                sedGaps.push_back(gap1);
                added = true;
            }
            if (gap2 > 0 && gap2 < n) {
                 // 避免重复添加 gap=1 (当k=0时两个公式都可能产生1)
                 if (gap1 != gap2) {
                     sedGaps.push_back(gap2);
                     added = true;
                 } else if (k==0 && gap2 == 1) { // Ensure 1 is added at least once
                     sedGaps.push_back(gap2);
                     added = true;
                 }
            }

            // 如果当前 k 生成的两个 gap 都大于等于 n, 且至少添加过一个gap, 则可以停止
            if ((gap1 >= n || gap1 <=0) && (gap2 >= n || gap2 <=0) && !sedGaps.empty() && k > 0) {
                 break;
            }
             // 如果n很小(e.g., n=1), 可能一个gap都没加进去就退出了, 需要特殊处理
            if (gap1 <= 0 && gap2 <= 0 && k > 5) break; // Safety break

            k++;
        }
        // 排序并去重
        std::sort(sedGaps.begin(), sedGaps.end());
        sedGaps.erase(std::unique(sedGaps.begin(), sedGaps.end()), sedGaps.end());

        // 转换回 int, 并再次过滤确保小于 n
        for (long long g : sedGaps) {
            if (g < n) {
                gaps.push_back(static_cast(g));
            }
        }
         std::reverse(gaps.begin(), gaps.end()); // 按降序使用
    }

    // 最后检查: 确保序列不为空 (除非 n=0 或 1), 且包含 1
    if (n > 1) {
        if (gaps.empty()) {
            gaps.push_back(1);
        } else {
            bool foundOne = false;
            for (int g : gaps) {
                if (g == 1) {
                    foundOne = true;
                    break;
                }
            }
            if (!foundOne) {
                gaps.push_back(1);
                // 如果添加了 1, 可能需要重新排序以保持降序
                std::sort(gaps.rbegin(), gaps.rend());
            }
        }
    } else {
        gaps.clear(); // n<=1 不需要排序, gap序列为空
    }


    return gaps;
}


/**
 * @brief 使用希尔排序算法对整数向量进行原地排序。
 * @param arr 要排序的向量 (通过引用传递，将被修改)。
 * @param sequenceType 要使用的增量序列类型 (默认为 "knuth")。
 */
void shellSort(std::vector& arr, const std::string& sequenceType = "knuth") {
    int n = arr.size();
    if (n <= 1) return; // 数组为空或只有一个元素，无需排序

    // 1. 获取增量序列
    std::vector gaps = generateGaps(n, sequenceType);

    // 2. 遍历每个增量 gap (从大到小)
    for (int gap : gaps) {
        // 3. 对当前 gap 执行分组插入排序
        //    从索引 gap 开始遍历数组
        for (int i = gap; i < n; ++i) {
            // a. 存储待插入元素
            int temp = arr[i];
            int j = i;

            // b. 在当前子序列 (间隔为 gap) 中向前查找插入位置
            //    比较 arr[j - gap] 与 temp
            while (j >= gap && arr[j - gap] > temp) {
                if (!isRunning) break;

                // c. 如果前面的元素更大，则将其后移
                arr[j] = arr[j - gap];
                j -= gap; // 向前移动 gap 步
            }

            // d. 将 temp 插入到找到的正确位置 j
            arr[j] = temp;
        }
        // 当这个内层 for 循环结束时, 数组对于当前的 gap 是部分有序的
    }
    // 当 gap = 1 时，执行最后一次插入排序，完成整个排序过程
}

// --- 示例用法 ---
/*
// 在 main 函数中使用
#include  // main 函数需要

// 可选的打印函数
void printVector(const std::vector& vec) {
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    using namespace std; // 使用命名空间 std 简化代码

    vector data = {34, 8, 64, 51, 32, 21, 7, 19, 45, 90, 1, 5};

    cout << "原始数组: ";
    printVector(data);

    shellSort(data, "sedgewick"); // 使用 Sedgewick 序列进行排序

    cout << "排序后数组: ";
    printVector(data);

    return 0;
}
*/