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;

不过，更重要的是，您的递归没有终止条件。当 right <= left.

时，您的 quickSort() 函数应该在不执行任何操作（尤其是不递归）的情况下终止

更新：

虽然我自己不会像这样实现它，但以下是我能想到的将起始代码转换为工作类型的最小更改：

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] 中保持到那时为止，循环结束后的两次交换才有意义。但是，这意味着内部循环中的比较必须与 those 值进行比较，而不是与 A[pLow] 和 A[pHigh].

进行比较

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

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

C: Trying to implement a dual-pivot quicksort but getting stuck in an infinite loop

c

quicksort

infinite-loop