C++如何实现希尔排序 C++希尔排序的算法与代码解析

#include <iostream>
#include <vector>

void shellSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

int main() {
    std::vector<int> arr = {12, 34, 54, 2, 3, 8, 90, 1};
    shellSort(arr);
    std::cout << "Sorted array: \n";
    for (int i = 0; i < arr.size(); i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
    return 0;
}

#include <iostream>
#include <vector>

void shellSortKnuth(std::vector<int>& arr) {
    int n = arr.size();
    std::vector<int> gaps;
    // Generate Knuth sequence
    for (int k = 1; k < n; k = k * 3 + 1) {
        gaps.push_back(k);
    }

    for (int i = gaps.size() - 1; i >= 0; --i) {
        int gap = gaps[i];
        for (int j = gap; j < n; j++) {
            int temp = arr[j];
            int k = j;
            while (k >= gap && arr[k - gap] > temp) {
                arr[k] = arr[k - gap];
                k -= gap;
            }
            arr[k] = temp;
        }
    }
}

int main() {
    std::vector<int> arr = {12, 34, 54, 2, 3, 8, 90, 1};
    shellSortKnuth(arr);
    std::cout << "Sorted array: \n";
    for (int i = 0; i < arr.size(); i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
    return 0;
}