尝试对大型已排序容器进行排序时，Quicksort会生成退出代码-1073741571（0xC00000FD）

Question

我试图实现一个工作快速排序，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，则会因上面的错误代码而崩溃

Answer 1

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

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

如果您的目标是从维基百科复制算法，那么您的代码就可以了，并且只是预期崩溃。如果您的目标是对数据进行排序，那么您复制的伪代码就不是很好。