C中分区函数的索引问题

Question

我正在尝试为要在我创建的Struct数组上运行的quicksort创建分区函数。但是，在运行时，索引突然变得奇怪而发疯。 （例如，在某个特定的bigger=bigger-1调用之后，bigger突然获得值0却没有明显的原因。

这是我的代码：

int partition(Student studentsArray[], int left, int right)
{
    Student tempArr[right+1 - left];
    int smaller = left; int bigger = right;
    for(int i =left; i<right;i++)
    {
        if(stringComperator(studentsArray[i].name,studentsArray[right].name)>0)
        {
            tempArr[bigger]=studentsArray[i];
            bigger=bigger-1;
        }
        else
        {
            tempArr[smaller]=studentsArray[i];
            smaller=smaller+1;
        }
    }
    tempArr[smaller]=studentsArray[right];
    for(int i=left;i<right-left+1;i++)
    {
        studentsArray[i]=tempArr[i];
    }
    return smaller;
}

Answer 1

您的代码在以下行中具有未定义的行为：

  tempArr[bigger]=studentsArray[i];

您的tempArr大小为right+1 - left，并且bigger开始等于right。这意味着当left > 0时，您超出范围。

在这些情况下可能发生的许多事情之一就是覆盖其他自动分配的变量，例如bigger。

---

解决它的几种方法包括对尺寸进行花式检查。但是，恕我直言，直接的方法是避免创建tempArr，并就地更新值。