c - QuickSort 无法正确排序

Question

我有一个程序来接收一个结构，存储它然后对其进行排序。我尝试过使用希尔排序，但后来我选择了快速排序算法。但是，当我尝试在排序后打印数组时，它仍然返回未排序的数组。请记住，我正在尝试按“num_aluno”对其进行排序。

代码

typedef struct ALUNO
{
char primeiro_nome[15];
char segundo_nome[15];
int num_aluno;
float nota;

}ALUNO;

void swap(ALUNO* a, ALUNO* b)
{
ALUNO t=*a;
*a=*b;
*b=t;
}
int partition(ALUNO *studentList, int low, int high)
{
int pivot= studentList[high].num_aluno;
int i=(low-1);
int j;

for(j=low;j<=high-1;j++)
{
    if(studentList[j].num_aluno<=pivot);
    {
        i++;
        swap(&studentList[i], &studentList[j]);
    }
}
swap(&studentList[i+1], &studentList[high]);
return(i+1);
}
void quickSort(ALUNO *studentList, int low, int high)
{
if(low<high)
{
    int pi=partition(studentList, low, high);

    quickSort(studentList, low, pi-1);
    quickSort(studentList, pi+1, high);
}
}

int main()
{
ALUNO *studentList=NULL;
int currentPos, studentListSize=1;
//float grade_sum=0;

studentList=(ALUNO*)calloc(studentList, studentListSize*sizeof(ALUNO));

printf("Insira o numero de alunos \n");
scanf("%d", &studentListSize);

studentList=(ALUNO*)realloc(studentList, studentListSize*sizeof(ALUNO));

for(currentPos=0;currentPos<studentListSize;currentPos++)
{
    newStudent(studentList, currentPos);
}

quickSort(studentList, 0, studentListSize);

for(currentPos=0;currentPos<studentListSize;currentPos++)
{
    printStudent(studentList,currentPos);
}

free(studentList);

return 0;
}

如有任何帮助，我们将不胜感激

Answer 1

它不对列表进行排序的原因是，i 和 j 在分区函数中始终是相同的值。

你应该从高位-1开始j，而不是从低位开始。 另外，您没有考虑 StudentList[i] 的值。必须保证它大于主元，否则可能有一个小于主元的值，但位于数组的左侧。

这里，更正一下。

    int partition(ALUNO*studentList, int low, int high)
{
    int pivot = studentList[high].num_aluno;
    int i=low ;
    int j;

    for(j=high-1;j>=i;)
    {
        while(studentList[i].num_aluno < pivot)
         i++;
        while(studentList[j].num_aluno > pivot)
         j--;


            if(i<=j){
            swap(&studentList[i], &studentList[j]);
            i++;
            j--;
            }


    }
    swap(&studentList[i], &studentList[high]);
    return(i+1);
}

如果您还没有听说过，请注意不要选择第一个或最后一个值作为主元。相反，请使用三个策略的中值。

中三策略:选取未排序数组中的第一个、中间和最后一个元素。根据它们的值以排序的方式更改它们的位置。然后取中间值并将其用作枢轴。这样您就可以避免 QuickSort 的最坏时间复杂度 (O(n^2))。