数组中位数求解函数Bug排查：排序失效与结果偏移问题

原代码存在的核心问题 #

1. 冒泡排序实现完全错误

   • 外层循环每次都重新创建并复制数组，且复制时仅遍历到length-1，导致x_copy的最后一个元素未初始化，为垃圾值。
   • 每轮外层循环都从原始数组重新开始，仅做了一次相邻元素交换，根本没有完成完整的冒泡排序流程，数组自然无法被正确升序排列。

2. 中位数索引计算错误

   • 当数组长度为奇数时，原代码用x_copy[length/2 - 1]取中位数，实际应该取x_copy[length/2]（unsigned整数除法下，比如长度为5时，5/2=2，对应数组中间位置的索引），导致结果偏移一位。

修正后的代码 #

double vect_median(const double x[], unsigned length)
{
    double ans = 0;
    // 一次性复制整个数组，避免重复创建和漏复制
    double x_copy[length];
    for (size_t j = 0; j < length; ++j)
    {
        x_copy[j] = x[j];
    }

    // 正确实现冒泡排序：外层循环控制排序轮数，共length-1轮
    for (unsigned i = 0; i < length - 1; ++i)
    {
        // 内层循环每轮减少i次比较，因为末尾i个元素已排好序
        for (size_t k = 0; k < length - 1 - i; ++k)
        {
            if (x_copy[k] > x_copy[k + 1])
            {
                double temp = x_copy[k];
                x_copy[k] = x_copy[k + 1];
                x_copy[k + 1] = temp;
            }
        }
    }

    // 修正中位数索引计算
    if (length % 2 == 0)
    {
        ans = (x_copy[length/2 - 1] + x_copy[length/2]) / 2.0;
    }
    else
    {
        ans = x_copy[length/2];
    }

    return ans;
}

修改说明 #

• 数组复制：将数组复制操作移到外层循环外，仅执行一次，且遍历到length确保所有元素都被复制。
• 冒泡排序逻辑：外层循环从0到length-2，控制排序轮数；内层循环每轮减少i次比较，利用冒泡排序的特性（每轮将最大元素移到末尾，后续轮无需再比较已排序的末尾元素），完成完整的升序排序。
• 中位数计算：奇数长度时取x_copy[length/2]，偶数长度时取中间两个元素的平均值（索引为length/2 -1和length/2），确保结果正确。

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