C:尝试实现双枢轴快速排序但陷入无限循环

Question

在写这篇文章之前，我试图找到一个用 C 实现的算法的例子，但在 google 上搜索了一段时间后找不到。尽管我可能不太熟悉编程术语，无法正确搜索它。该代码基于有关算法的论文(Java 示例)和我找到的另一个 Java 实现。

它目前陷入无限循环，但我很难找到原因。部分原因可能是因为我尝试将代码转换为 C，但犯了错误。

#include <stdio.h>

void printArray(int A[], int size) {
    printf("[ ");
    int i = 0;
    for (i = 0; i < size; i++) {
        printf("%d", A[i]);
        if (i < size - 1) printf(", ");
    }
    printf(" ]\n");
}

void quickSort(int A[], int left, int right) {
    if (right <= left ) return;

    int temp;

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

    int pLow = left + 1;
    int pHigh = right - 1;
    int i = left + 1;

    while (i <= pHigh) {
        if (A[i] < A[pLow]) {
            temp = A[i];
            A[i] = A[pLow];
            A[pLow] = temp;
            A[pLow++];
            i++;
        }
        else if (A[pHigh] < A[i]) {
            temp = A[i];
            A[i] = A[pHigh];
            A[pHigh] = temp;
            A[pHigh--];
        }
        else i++;
    }

    temp = A[left];
    A[left] = A[--pLow];
    A[pLow] = temp;
    temp = A[right];
    A[right] = A[++pHigh];
    A[pHigh] = temp;

    quickSort(A, left, pLow-1);
    if (A[pLow] < A[pHigh]) quickSort(A, pLow+1, pHigh-1);
    quickSort(A, pHigh+1, right);
}

int main() {
    int size = 10;
    int array[10] = {1, 0, 7, 9, 6, 2, 5, 8, 4, 3};

    printf("Before: ");
    printArray(array, size);

    quickSort(array, 0, size-1);

    printf("After: ");
    printArray(array, size);

}

Answer 1

这很可疑......

int pLow = left + 1;
int pHigh = right - 1;

...当您刚刚不厌其烦地确保 A[left] < A[right] ，但没有采取任何措施来测试或修复 A[left + 1] 的相对顺序和A[right - 1] 。我认为您想从子数组的最末端选择枢轴:

int pLow = left;
int pHigh = right;

更重要的是，您的递归没有终止条件。您的quickSort()当 right <= left 时，函数应该终止而不做任何事情(特别是不递归) .

更新:

虽然我自己不会像这样实现它，但以下代表了我可以想出的将起始代码转换为工作类型的最小更改:

void quickSort(int A[], int left, int right) {
    int temp;

    if (right <= left) return;

    if (A[right] < A[left]) {
        temp = A[right];
        A[right] = A[left];
        A[left] = temp;
    }
    /* A[left] and A[right] are the left and right pivot values */

    int pLow = left + 1;
    int pHigh = right - 1;
    int i = left + 1;

    while (i <= pHigh) {
        if (A[i] < A[left]) {
            temp = A[i];
            A[i++] = A[pLow];
            A[pLow++] = temp;
        }
        else if (A[right] < A[i]) {
            temp = A[i];
            A[i] = A[pHigh];  /* i not incremented here */
            A[pHigh--] = temp;
        }
        else i++;
    }

    temp = A[left];
    A[left] = A[--pLow];
    A[pLow] = temp;
    temp = A[right];
    A[right] = A[++pHigh];
    A[pHigh] = temp;

    quickSort(A, left, pLow - 1);
    if (A[pLow] < A[pHigh]) quickSort(A, pLow + 1, pHigh - 1);
    quickSort(A, pHigh + 1, right);
}

特别注意，只有当主元值保持在 A[left] 中时，循环结束后的两次交换才有意义。和A[right] 。但是，这意味着内部循环中的比较必须与那些值进行比较，而不是与 A[pLow] 进行比较。和A[pHigh] .

我将原始初始化保留为 pLow和pHigh (尽管我之前有评论)；因此，这些代表低分区和高分区中下一个可用位置的索引。我还更改了一些增量和减量。