快速排序不排序高范围的数字

Question

void quickSort(vector<long>& numberList,long low, long high){
    long pivot, indexLow, indexHigh, temp;

    if(low<high){
        pivot = low;
        indexLow = low;
        indexHigh = high;

        while(indexLow<indexHigh){
            while(numberList[indexLow] <= numberList[pivot]){
            indexLow++;
            }
            while(numberList[indexHigh] > numberList[pivot]){
            indexHigh--;
            }

            if(indexLow<indexHigh){
                temp = numberList[indexLow];
                numberList[indexLow] = numberList[indexHigh];
                numberList[indexHigh] = temp;
                }
        }

        temp = numberList[pivot];
        numberList[pivot] = numberList[indexHigh];
        numberList[indexHigh] = temp;

        quickSort(numberList, low, indexHigh-1);
        quickSort(numberList, indexHigh+1, high);
    }
}

此代码完美地对给定的数字列表进行排序，直到 10000，但我尝试使用 100000，但程序终止了，你能告诉我我做错了什么吗？

Answer 1

对于10^5个元素，递归例程调用过多会超出函数栈容量，导致栈溢出。像快速排序的最坏情况（当所有元素都已经排好O(n^2)），递归关系是T(n) = T(n - 1) + Θ(n)，这肯定会导致堆栈溢出。实际上，10^5 也足以在 best/average 情况下导致堆栈溢出 (O(n logn))。如果您的容器太大，请使用迭代方法进行快速排序。

Answer 2

~~您的程序中肯定存在错误：http://ideone.com./W0Chni~~

~~我只对 10 个元素 2-1-3-8-1-6-8-9-9-9 进行排序，它在崩溃前不久以 indexLow 为 11 结束。~~

对不起，我的错，它工作正常。

我认为这可能是堆栈溢出。您可以通过采用不同的支点（无论如何都应该）来减轻这种可能性，但避免堆栈溢出的最佳方法是使用堆栈数据结构而不是递归：

将您的初始 {low,high} 压入堆栈
将您的函数包装在一个 while 循环中，直到堆栈为空。每次迭代都会将栈顶的 {low,high} 弹出。
不是递归，而是将成对的 {low,high} 压入堆栈。

像这样：http://ideone.com/gwWSjV

void quickSort(std::vector<long>& numberList, long low, long high)
{
    struct lh { long low; long high; };
    std::vector<lh> stack;
    stack.push_back(lh{low, high});

    while (!stack.empty())
    {
        lh popped = stack.back();
        stack.pop_back();
        low = popped.low;
        high = popped.high;

        long pivot, indexLow, indexHigh, temp;

        if(low<high){
            pivot = low;
            indexLow = low;
            indexHigh = high;

            while(indexLow<indexHigh){
                while(numberList[indexLow] <= numberList[pivot]){
                indexLow++;
                }
                while(numberList[indexHigh] > numberList[pivot]){
                indexHigh--;
                }

                if(indexLow<indexHigh){
                    temp = numberList[indexLow];
                    numberList[indexLow] = numberList[indexHigh];
                    numberList[indexHigh] = temp;
                    }
            }

            temp = numberList[pivot];
            numberList[pivot] = numberList[indexHigh];
            numberList[indexHigh] = temp;

            //quickSort(numberList, low, indexHigh-1);
            stack.push_back(lh{low, indexHigh-1});

            //quickSort(numberList, indexHigh+1, high);
            stack.push_back(lh{indexHigh+1, high});
        }
    }
}

瞧：不再需要递归，可以毫不费力地对 1,000,000 个元素进行排序。

您可以通过仅将第二个递归压入堆栈然后立即循环返回执行第一个递归而不用 push/pop 来优化它，但这并不是一个巨大的收获。

Answer 3

对于快速排序而言，取得良好的枢轴非常重要。您正在使用第一个元素（实际上是 low）：

pivot = low;

因此，您得到的递归深度为 100000，因此它的堆栈溢出。

Answer 4

虽然它可能像其他人所说的那样是堆栈溢出，但我对此表示怀疑。您的代码有一些错误，可能会导致它访问数组中超出边界的位置，这将（可能但不能保证）提示因分段错误而提前终止（或者在其他情况下它似乎可以正常工作，这就是 UB 的原因太糟糕了）。

考虑一下：

while(numberList[indexLow] <= numberList[pivot]){
    indexLow++;
}
while(numberList[indexHigh] > numberList[pivot]){
    indexHigh--;
}

如果数组中的每个数字都已经小于或等于 numberList[pivot] 怎么办？ indexLow 将愉快地递增超过 high，这很可能是数组的大小。您需要在两个循环中检查外循环条件是否仍然存在。所以，改为这样做：

while (indexLow < indexHigh && numberList[indexLow] <= numberList[pivot]) {
    indexLow++;
}
while (indexHigh > indexLow && numberList[indexHigh] > numberList[pivot]) {
    indexHigh--;
}

这确保内部循环不会使外部条件无效；没有这个，所有关于为什么你的代码被破坏/不工作的赌注都没有了。

然后我们有这个：

temp = numberList[pivot];
numberList[pivot] = numberList[indexHigh];
numberList[indexHigh] = temp;

现在，如果您像我说的那样修复循环，这可能会有问题。循环可能已经停止，因为每个元素都小于或等于主元（在这种情况下，执行此交换操作是安全的），但循环可能已经停止，因为 indexLow 和 indexHigh 发生了冲突，在这种情况下，我们不知道 numberList[indexLow] 是否实际上大于主元，或者它是否仍然小于或等于主元。所以我们需要手动测试它，并且可能会递减 indexLow 以找到要交换枢轴的值：

assert(indexLow == indexHigh);
assert(indexLow > low);

if (numberList[indexLow] > numberList[pivot])
    indexLow--;

assert(numberList[indexLow] <= numberList[pivot]);

temp = numberList[pivot];
numberList[pivot] = numberList[indexLow];
numberList[indexLow] = temp;

quickSort(numberList, low, indexLow-1);
quickSort(numberList, indexLow+1, high);

这是包含这些修复的完整版本：

void quickSort(vector<long> &numberList, long low, long high) {
    long pivot, indexLow, indexHigh, temp;
    if (low<high) {
        pivot = low;
        indexLow = low;
        indexHigh = high;

        while (indexLow < indexHigh) {
            while (indexLow < indexHigh && numberList[indexLow] <= numberList[pivot]) {
                indexLow++;
            }
            while (indexHigh > indexLow && numberList[indexHigh] > numberList[pivot]) {
                indexHigh--;
            }

            if (indexLow < indexHigh) {
                temp = numberList[indexLow];
                numberList[indexLow] = numberList[indexHigh];
                numberList[indexHigh] = temp;
            }
        }

        assert(indexLow == indexHigh);
        assert(indexLow > low);

        if (numberList[indexLow] > numberList[pivot])
            indexLow--;

        assert(numberList[indexLow] <= numberList[pivot]);

        temp = numberList[pivot];
        numberList[pivot] = numberList[indexLow];
        numberList[indexLow] = temp;

        quickSort(numberList, low, indexLow-1);
        quickSort(numberList, indexLow+1, high);
    }
}

请注意，此实现比平时复杂多了。像这样在数组中前后移动并不会真正获得太多收益。传统的实现代码更简单，更容易阅读和理解：

void quicksort_simpler(vector<long> &numberList, long low, long high) {
    if (low >= high)
        return;

    long pivot = low;
    long last = pivot;
    long i;

    for (i = pivot+1; i <= high; i++) {
        if (numberList[i] <= numberList[pivot]) {
            last++;
            swap(numberList[last], numberList[i]);
        }
    }

    swap(numberList[last], numberList[pivot]);

    quicksort_simpler(numberList, low, last-1);
    quicksort_simpler(numberList, last+1, high);
}

确保包含 <algorithm> 以获得 swap() 的声明。

快速排序不排序高范围的数字

Quick Sort not sorting numbers of high range

c++

algorithm

vector

quicksort