如何将迭代实现的ShellSort算法改写为递归形式？

要把迭代版希尔排序改成递归，核心是将三层循环分别转化为递归调用，每层循环对应明确的终止条件和递归步骤：

拆解原迭代逻辑 #

原迭代版希尔排序的三层循环职责：

1. 外层循环：控制步长gap从num/2开始，每次减半直到gap>0
2. 中间循环：对每个步长gap，从j=gap开始遍历数组所有待处理元素
3. 内层循环：对每个j，向前以gap为步长比较交换，直到元素处于有序位置

递归实现代码 #

// 内层递归：处理单个元素的向前插入（对应原内层k循环）
void insertElementRecursive(int *arr, int gap, int k) {
    // 终止条件：k越界或当前元素无需交换
    if (k < 0 || arr[k + gap] >= arr[k]) {
        return;
    }
    // 沿用原逻辑的加减交换方式
    arr[k] = arr[k] + arr[k + gap];
    arr[k + gap] = arr[k] - arr[k + gap];
    arr[k] = arr[k] - arr[k + gap];
    // 递归处理前一个步长位置
    insertElementRecursive(arr, gap, k - gap);
}

// 中间层递归：处理当前步长下的所有元素（对应原中间j循环）
void insertionSortRecursive(int *arr, int num, int gap, int j) {
    // 终止条件：j遍历完数组
    if (j >= num) {
        return;
    }
    // 处理当前j位置的元素插入逻辑
    insertElementRecursive(arr, gap, j - gap);
    // 递归处理下一个j
    insertionSortRecursive(arr, num, gap, j + 1);
}

// 外层递归：控制步长变化（对应原外层i循环）
void ShellSortRecursive(int *arr, int num, int gap) {
    // 终止条件：步长为0，排序完成
    if (gap <= 0) {
        return;
    }
    // 处理当前步长下的插入排序
    insertionSortRecursive(arr, num, gap, gap);
    // 递归处理减半后的步长
    ShellSortRecursive(arr, num, gap / 2);
}

// 对外接口，与原函数参数完全一致，可直接替换使用
void ShellSort(int *arr, int num) {
    if (num <= 1) {
        return;
    }
    // 初始步长设为num/2，启动递归
    ShellSortRecursive(arr, num, num / 2);
}

代码说明 #

• insertElementRecursive：替代原内层k循环，负责以指定步长向前比较交换，直到元素处于正确位置
• insertionSortRecursive：替代原中间j循环，遍历每个待处理元素，调用内层递归完成插入操作
• ShellSortRecursive：替代原外层i循环，控制步长从初始值逐步减半，直到步长为0时终止递归
• 对外接口ShellSort保持了和原函数相同的参数结构，不需要修改调用逻辑即可替换使用

内容的提问来源于stack exchange，提问作者Cris