为什么"middle = arr[(beg + end) / 2]"会出错？

Question

我用c实现了quick_select，但是我的代码出错了，我花了很长时间才找出原因，但我仍然无法理解。

get_pivot函数是为quick_select找到一个透视，这是错误的代码：

int get_pivot(int*arr, int beg, int end)
{
    int middle = arr[(beg + end) / 2];                    
    if (middle < arr[beg])
      swap(&middle, &arr[beg]);
    if (arr[end] < arr[beg])
      swap(&arr[beg], &arr[end]);
    if (middle>arr[end])
      swap(&middle, &arr[end]);
    swap(&middle, &arr[end - 1]);
    return arr[end - 1];
}

此函数旨在找出 3 的中间数字并将枢轴移动到末尾。

但是，它出错了(我的意思是quick_select输出未排序数组(，直到我int middle = arr[(beg + end) / 2];用 int middle=(beg+end)/2并使用arr[middle]而不是middle。这是正确的代码：

int get_pivot(int*arr, int beg, int end)
{
    int middle = (beg + end) / 2;                  
    if (arr[middle] < arr[beg])
        swap(&arr[middle], &arr[beg]);
    if (arr[end] < arr[beg])
        swap(&arr[beg], &arr[end]);
    if (arr[middle]>arr[end])
        swap(&arr[middle], &arr[end]);
    //hide pivot
    swap(&arr[middle], &arr[end - 1]);
    return arr[end - 1];
}

我不明白为什么int middle = arr[(beg + end) / 2];会出错。

我真的很感谢你的帮助！

Answer 1

由于这一行(以及后面的类似行(而出错

swap(&middle, &arr[beg]);

middle是一个单独的变量，当你使用上述方式交换时，数组中的实际元素(array[middle](不会被交换(你需要(。

---

您希望交换数组的索引beg和middle中的元素。这可以通过做

swap(&arr[middle], &arr[beg]);