C中分区函数的索引问题

Question

我试图为我想运行我创建的结构数组创建一个快速排序分区函数。然而，在运行时间里，索引突然变得异常和疯狂。（例如，在某个 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;
}

编辑： 更新代码：似乎在方法内部工作，但似乎 studentsArray 不会在函数调用之外更改它的值。

void swap(Student* a, Student* b)
{
    Student temp = *a;
    *a = *b;
    *b = temp;
}

int partition(Student studentsArray[], int left, int right)

{
    Student pivot = studentsArray[right];
    int i = left;
    for(int j = 0; j<right;j++)
    {
        if(stringComperator(studentsArray[j].name,pivot.name)<0)
        {
            swap(&studentsArray[i],&studentsArray[j]);
            i=i+1;
        }
    }
    swap(&studentsArray[i],&pivot);
    return i;
}

Answer 1

您的代码中有 未定义的行为，例如：

  tempArr[bigger]=studentsArray[i];

您的 tempArr 尺寸为 right+1 - left，bigger 开始时等于 right。这意味着当left > 0时，你出界了。

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

解决它的方法很少，包括迂腐地检查尺寸。但是，恕我直言，直接的方法是避免创建 tempArr，并就地更新值。

C中分区函数的索引问题

Index problems with partition function in C

c

sorting

quicksort