C++实现希尔排序

好的，以下是C++实现希尔排序的代码：

void shellSort(int arr[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i += 1) {
            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;
        }
    }
}

在希尔排序中，我们使用一个间隔序列来将数组划分为若干个子序列，对每个子序列进行插入排序，直到间隔序列为1时，整个数组就已经有序了。在实现中，我们使用一个循环来不断缩小间隔序列，每次循环都对当前间隔下的子序列进行插入排序。

相关问题

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

希尔排序（Shell Sort），也称为缩小增量排序，是一种基于插入排序的优化版本。它通过将待排序的数据分组，先对每组进行插入排序，然后逐步减小组距，直到组距为1，完成整个序列的排序。以下是C++实现希尔排序的一个简单版本：

#include <iostream>
#include <vector>

void shellSort(std::vector<int>& arr, int gap = 1) {
    // 循环直到组距变为1
    while (gap > 0) {
        // 对当前组距进行插入排序
        for (int i = gap; i < arr.size(); ++i) {
            int temp = arr[i];
            int j;
            // 将temp元素插入到已排序部分的正确位置
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
        // 减少组距以便处理更紧密的子数组
        gap /= 2;
    }
}

// 示例使用
int main() {
    std::vector<int> nums = {9, 7, 5, 11, 12, 2, 14, 3};
    std::cout << "Before sorting:\n";
    for (const auto& num : nums)
        std::cout << num << ' ';
    std::cout << '\n';

    shellSort(nums);
    std::cout << "After sorting:\n";
    for (const auto& num : nums)
        std::cout << num << ' ';
    stdollars "\n";

    return 0;
}

在这个例子中，`shellSort`函数接受一个整数向量和可选的初始组距`gap`。当`gap`减少到1时，整个序列就被认为是有序的。

c++代码实现希尔排序

C++中的希尔排序通过分组的方式优化了插入排序，它的基本思想是从大到小设置增量序列，依次对每组进行插入排序。以下是一个简单的希尔排序实现[^1]：

// 声明模板函数，接受任意类型的T并传入待排序数组和其长度
template<typename T>
void shellsort(T D[], int n) {
    // 初始增量设为数组的一半，逐渐减小直到1
    int gap = n / 2;
    
    // 当增量大于0时，执行循环
    while (gap > 0) {
        for (int i = gap + 1; i < n; ++i) {
            // 使用临时变量存储当前元素，与前面元素比较
            T temp = D[i];
            
            // 如果当前元素小于前一个元素，交换它们的位置
            for (int j = i - gap; j >= 0 && temp < D[j]; j -= gap) {
                D[j + gap] = D[j];
            }
            // 放回原始位置
            D[j + gap] = temp;
        }
        // 缩小增量，继续下一轮排序
        gap /= 2;
    }
}

// 示例使用
int main() {
    int arr[] = {9, 7, 5, 11, 12, 2, 14, 3};
    int n = sizeof(arr) / sizeof(arr);
    shellsort(arr, n);
    // 打印排序后的数组
    for (int i = 0; i < n; ++i)
        std::cout << arr[i] << " ";
    return 0;
}