algorithm - 这个快速排序实现的错误是什么？

Question

该代码适用于少数测试用例，但对大多数测试用例都失败了。我哪里弄错了？

此外，如果可以采取任何措施使代码更高效。

void quicksort(int *a, int a1, int b1)
{
if ((b1 - a1) > 0)
{
    int pivot = (a1 + b1) / 2;
    int i = a1;
    int j = b1;
    while (i <= j)
    {
        while (a[i] < a[pivot]) //left to right
            i++;
        while (a[j] > a[pivot]) //right to left
            j--;
        if (i < j) // swapping
        {
            int temp;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }

    }
    quicksort(a, a1, j);
    quicksort(a, i, b1); //recursive calls
}

Answer 1

您不考虑 i == j 时的情况而且，正如@MK 在评论中所说，枢轴应该是一个值而不是索引( pivot = (a1+b1)/2; 应该类似于 pivot = a[(a1+b1)/2] )。

例如，如果您启动数组 a = {2, 45, 56, 3, 125} (您在评论中指出的数组)您的实现可以转换为 {2, 3, 45, 56, 125}与 i = 2 , j = 2 , 还有 pivot = 2 (作为索引处理)。在这种情况下，程序将进入无限循环，因为它永远不会进入最后一个 if。 block 。

如果将内部 if 的条件更改为 i <= j应该是正确的。

最后，还应用一些小的优化，您的代码应如下所示:

void quicksort(int *a, int a1, int b1)
{
    if (b1 > a1)    // one less operation (subtraction) with respect to the original
    {
        int pivot = a[a1 + ((b1 - a1) / 2)];    // it is now a value and not an index. the index is calculated in this way to avoid an arithmetic overflow
        int i = a1;
        int j = b1;
        while (i <= j)
        {
            while (a[i] < pivot) //left to right
                i++;
            while (a[j] > pivot) //right to left
                j--;
            if (i <= j) // swapping
            {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            }
        }
        quicksort(a, a1, j);
        quicksort(a, i, b1); //recursive calls
    }
}

作为最后的优化，我建议 optimize the tail call .

如果有任何不清楚的地方，请告诉我。