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;
}