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

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 块。

如果将内部 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。

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

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

What is the mistake in this quicksort implementation?

sorting

algorithm

debugging

quicksort