C++中Stooge Sort算法里ceil()函数计算异常问题

你的Stooge Sort实现目前存在两个关键问题，我来帮你逐一梳理并解决：

1. mid值计算的核心问题 #

你当前的int mid = (int) ceil((2 * size) / 3)写法有两个明显缺陷：

• 在C语言中，(2 * size)/3属于整数除法，会自动截断小数部分（比如size=4时，2*4=8，8/3直接得到2，而非实际需要的2.666...）。此时再用ceil()处理这个整数，结果不会有任何变化，导致mid无法得到正确的向上取整值。
• 就算修正了浮点运算逻辑，直接基于size得到的mid也没有结合当前子数组的low索引，会导致递归区间的定位完全偏移。

最优修正：用整数运算模拟向上取整 #

对于正整数a和b，ceil(a/b)可以通过(a + b - 1) / b来实现，完全避免浮点运算的误差。针对我们需要的ceil(2*size/3)，可以简化写成：

int k = (2 * size + 2) / 3;

2. 子数组元素交换的索引错误 #

你的代码在size == 2时，直接比较arr[0]和arr[1]，这只在初始调用（low=0）时有效。当递归到非起始位置的子数组（比如low=2、high=3）时，应该比较的是当前子数组的首尾元素arr[low]和arr[high]，而非固定的0、1索引。

修复后的完整代码 #

#include <stdio.h>

void stoogeSort(int arr[], int low, int high) {
    int size = high - low + 1;
    // 修正：比较当前子数组的首尾元素
    if (size == 2 && arr[low] > arr[high]) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    } else if (size > 2) {
        // 用整数运算计算ceil(2*size/3)
        int k = (2 * size + 2) / 3;
        // 递归排序前k个元素：low 到 low + k -1
        stoogeSort(arr, low, low + k - 1);
        // 递归排序后k个元素：high - k +1 到 high
        stoogeSort(arr, high - k + 1, high);
        // 再次递归排序前k个元素
        stoogeSort(arr, low, low + k - 1);
    }
}

// 测试用例
int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    stoogeSort(arr, 0, n-1);
    printf("排序后的数组：");
    for(int i=0; i<n; i++){
        printf("%d ", arr[i]);
    }
    return 0;
}

效果验证 #

比如当size=4时，k=(2*4+2)/3=10/3=3，刚好符合ceil(8/3)=3的预期，递归区间会正确划分为前3个元素和后3个元素（重叠1个元素），完全匹配Stooge Sort的核心逻辑。

内容的提问来源于stack exchange，提问作者J.Einhorn