带尾递归的 C++ 快速排序

Question

大家好，

我在使用 C++ 进行快速排序时遇到了一些问题。在排序数组的最坏情况下(值增加或减少)，我在包含 ~900 个元素的数组中得到 stackoverflow。尾递归是我找到的一个解决方案，但我可能不会在这里这样做，因为我没有实现任何改进:

void quickSort(int *array, int start, int end){
    //elementary state
    if (start + 1 > end){
        return;
    }

    //partitioning, retuns position of pivotelemnt
    int wall = partitioning(array, start, end);

    //recursion
    quickSort(array, start, wall-1);
    //tail recursion?
    return quickSort(array, wall + 1, end);
}//quickSort

正在关注 this Wikipedia article我刚刚将 return 添加到我最后一次调用 quickSort 作为那里的第一个例子。我不认为那有任何作用......

编辑:

int partitioning(int *array, int start, int end){

    //partitioningborder
    int wall = start;

    for (int i = wall; i < end; ++i){
        if (array[i] <= array[end]){

            //swap an element if needed
            int swap = array[i];
            array[i] = array[wall];
            array[wall] = swap;

            //increment the partitioningborder
            wall++;
        }//if
    }//for

    //place pivotelement
    int swap = array[end];
    array[end] = array[wall];
        array[wall] = swap;

        return wall;
}//partitioning

Answer 1

为避免堆栈溢出，代码需要比较分区大小，(wall - start) 与 (end - wall)，递归较小的分区，并循环返回较大的分区。这不是真正的尾递归。像这样:

void quickSort(int *array, int start, int end){
    while(start < end){
        wall = partition(...);   // wall = index to pivot
        // recurse on smaller part, loop on larger part
        if((wall - start) <= (end - wall)){
            quickSort(a, start, wall-1);
            start = wall+1;
        } else {
            quickSort(a, wall+1, end);
            end = wall-1;
        }
    }
}

如果使用 Hoare 类型的分区方案，wall 或 wall+1 可能指向枢轴值。您可以在分区中添加一个检查，以便返回的索引始终指向枢轴值(而不是有时指向枢轴值之前的 1)。