c - 在快速排序(hoare)中遇到无限循环，但我似乎没有发现问题

Question

所以，我写了一个快速排序算法和一个霍尔分区算法。不知何故，当我尝试在 main () 中运行示例案例时，它卡在了 fastSort(test, 0,3) 上。似乎存在无限循环。我不知道如何修复它，因为这两个函数单独看起来都很好。

我尝试过调试，但我对 c 还很陌生。我注意到 QuickSort(test,0,3) 递归地调用自身。所以我知道这个问题与高而不是下降有关。但我从大学幻灯片中获取了示例伪代码来构建该函数，一切似乎都一致。

void printArray(int A[], int high) {
    for (int i=0; i<=high; i++) {
         printf("%d ", A[i]);
    }
}

int partitionHoare(int A[], int low, int high) {
    int pivot=A[low];
    int left = low-1;
    int right= high+1;

    while (1){
        while (1){
            left++;
            if (A[left]>=pivot) break;
        }
        while (1){
            right--;
            if (A[right]<=pivot) break;
        }


        if (left<right)  {
            int temp=A[left];
            A[left]=A[right];
            A[right]=temp;
        }
        else return left;
    }
}

void quicksort(int A[], int low, int high){
    if (low<high){
        int middle=partitionHoare(A,low, high);
        quicksort(A, low,middle-1);
        quicksort(A, middle, high);
    }
}


void main (){
    int test[]={64,81,24,42,90,30,9,95};
    quicksort(test,0,7);
    printArray(test,7);

我实际上希望测试数组按如下方式打印出来:“9、24、30、42、64、81、90、95”

Answer 1

您的 quicksort() 函数存在逻辑缺陷:

void quicksort(int A[], int low, int high){
    if (low<high){
        int middle=partitionHoare(A,low, high);
        quicksort(A, low,middle-1);
        quicksort(A, middle, high);
    }
}

它不能确保递归会终止。

具体来说，如果在某个长度大于 1 的子数组中，第一个元素是最小的且不是重复的，则 partitionHoare() 将返回等于 low 的值 无需修改数组。在这种情况下，对左子数组的递归调用将不会执行任何操作，但对右子数组的递归调用将准确地重申当前参数。一切都没有改变，同样的事情肯定会再次发生，一次又一次，无限期地发生。

在这种情况下，您可以通过在 quicksort() 中测试是否 middle == low 来打破无限递归，但这不会给您正确的排序。

这里的一个常见解决方案有两个:

1. 确保分区函数将主元值交换为其报告的主元索引。这肯定是该值的正确最终位置。
2. 递归时，从两个子数组中排除主元索引(我们知道其值是正确的)，这样每个子问题都一定小于父问题。