时间戳

首页 > 解决方案 > 尝试对大型已排序容器进行排序时，快速排序生成退出代码 -1073741571 (0xC00000FD)

c++ - 尝试对大型已排序容器进行排序时，快速排序生成退出代码 -1073741571 (0xC00000FD)

问题描述

我试图实现一个有效的快速排序，Lomuto 变体。我正在使用来自维基百科的伪代码。https://en.wikipedia.org/wiki/Quicksort

void quickSortLomuto(int *first, int *last) {
    if(first < last){
        int *pivot= partitionLomuto(first,last);
        quickSortLomuto(first, pivot- 1);
        quickSortLomuto(pivot+ 1,last);
    }
}
int* partitionLomuto(int* first, int* last) {
    int pivot = *last;
    int *i = first;
    for(int* j = first;j <= last -1;j++){

        if(*j < pivot){
            std::swap(*i,*j);
            i++;
        }
    }
    std::swap(*i,*last);
    return i;
}

它适用于具有随机数的大型容器。它分解并为已排序的容器生成退出代码 -1073741571 (0xC00000FD)。对于非常小的排序容器，它可以工作，但如果容器的大小大于 1 00 000，它会崩溃并出现上面的错误代码

标签： c++quicksort

解决方案

原因有两个：首先，您使用了最差的枢轴值。对于已经排序的数组，它需要 O (n^2) 的执行时间。常用的策略是使用随机项作为枢轴值，或中间项，或第一个、最后一个和中间项的中值。

另一个原因是您的堆栈溢出，因为您执行递归的方式。为避免这种情况：找到较小的范围并递归排序。然后通过更改“first”和“last”参数对更大的范围进行排序，而不是使用递归，而是在同一函数内。这样，堆栈的深度最多为 log n。

如果您的目标是从 Wikipedia 复制算法，那么您的代码很好，并且崩溃是意料之中的。如果您的目标是对数据进行排序，那么您复制的伪代码就不是很好。

推荐阅读