无限循环中的快速排序结果

Question

我已经尽力了。甚至找到了一个与我完全一样的在线示例。每次我运行这种快速排序时，都会导致无限循环，我非常困惑。有人可以帮忙吗？我只是像往常一样传递一个数组，而无法使这种想法起作用。还要忽略时序方面，即项目的时序方面。

template<typename T>
void quickSort(T list[], int lowerBound, int upperBound)
{
    cout.setf(ios::fixed | ios::showpoint);
    cout.precision(16);

    TimerSystem timer;
    timer.startClock();

    upperBound = upperBound - 1;

    long int i = lowerBound;
    long int j = upperBound;
    long int pivot = list[(lowerBound + upperBound) / 2];
    T temp;

    while (i <= j)
    {
        while (list[i] < pivot)
        {
            i += 1;
        }

        while (list[j] > pivot)
        {
            j -= 1;
        }

        if (i <= j)
        {
            temp = list[i];
            list[i] = list[j];
            list[j] = temp;
            i += 1;
            j -= 1;
        }
    }

    if (lowerBound < j)
    {
        quickSort(list, lowerBound, j);
    }

    if (i < upperBound)
    {
        quickSort(list, i, upperBound);
    }


    cout << "USE FINAL TIME RECORDING!! QuickSort took " << timer.getTime() << "seconds to sort" << endl;
    cout << endl;
}

Answer 1

乍一看，

while (i <= j)

看起来可疑，请替换为

while (i < j)

然后重试。

Answer 2

由于代码使用cout.precision（16），所以我假设list []是一个浮点数或双精度数组。但是，将数据透视表定义为long int类型，而应将其键入为T：

    T pivot = list[(lowerBound + upperBound) / 2];

具有支点类型为long int的类型将解释无限循环，因为如果list [i] ==支点和/或list [j] ==支点，则内部while循环依赖于停止，如果实际枢纽：list [（lowerBound + upperBound）/ 2]不完全等于整数。

另一个问题是上限=上限-1;这将在quickSort的每个递归实例的初始位置发生。相反，应删除该语句，并且对大小为N的列表的初始调用应为

    quickSort(list, 0, N-1);

无需将i和j输入为int的长整数，只需将其输入为int就足够了，但这不会引起任何问题。