c++ - C++ 大数快速排序堆栈溢出

Question

美好的一天 我正在尝试对 10000 个数字使用快速排序，但它给了我堆栈溢出错误。它适用于随机数，但不适用于降序和升序数字。

' 谢谢

void quickSort(long* array, long start, long last)
{
    if (start < last)
    {
        int p = partition(array, start, last);
        quickSort(array, start, p-1);
        quickSort(array, p + 1, last);
    }
}
int partition(long* array, long start, long last)//first partition
{
    int j = start + 1;
    for (long i = start + 1;i <= last;i++)
    {
        if (array[i] < array[start])
        {
            swap(array[i], array[j]);
            j++;
        }           

    }
    swap(array[start], array[j - 1]);
    return j - 1;
}
'

Answer 1

对于已排序的元素，可以通过选择 array[start]、array[last] 和 array[( 三个元素的中位数来避免此问题start + last + 1)/2] 作为您的枢轴值。

int median_of_3(long* array, long start, long last)
{
    long a = (start + last + 1)/2, b = start, c = last;
    if (array[c] < array[a]) swap(array[c], array[a]);
    if (array[b] < array[a]) swap(array[b], array[a]);
    if (array[c] < array[b]) swap(array[c], array[b]);
    return partition(array, start, last);
}

避免大堆栈深度的另一种策略是计算哪个分区较小，并递归调用较小的分区。然后可以将另一个分区优化为循环(尾递归优化)。

void quickSort(long* array, long start, long last)
{
    if (start >= last) return;

    int p = median_of_3(array, start, last);
    int next_start[2] = { start, p + 1 };
    int next_last[2] = { p - 1, last };
    bool i = p > (start + last)/2;
    quickSort(array, next_start[i], next_last[i]);
    /*
     * If the compiler does not optimize the tail call below into
     * a loop, it is easy to do the optimization manually.
     */
    quickSort(array, next_start[!i], next_last[!i]);
}

自省(introspection)也可以用来避免大的堆栈深度。您跟踪递归调用深度，如果它“太深”，您将无法安全地使用不同的排序策略，例如合并排序或堆排序。这是 std::sort 当前使用的行为。

void introSortImpl(long* array, long start, long last, int depth)
{
    if (--depth == 0) {
        heapSort(array, start, last);
        return;
    }

    if (start >= last) return;

    int p = median_of_3(array, start, last);
    int next_start[2] = { start, p + 1 };
    int next_last[2] = { p - 1, last };
    bool i = p > (start + last)/2;
    introSortImpl(array, next_start[i], next_last[i], depth);
    introSortImpl(array, next_start[!i], next_last[!i], depth);
}

void introspectionSort(long* array, long start, long last)
{
    introSortImpl(array, start, last, log2(start - last) * 3);
}