Quicksort 给出常量而不是随机数的 stackoverflow

Question

当我用 rand() 或任何常量值分配数组值时，为什么这个 C++ 代码片段的行为不同，我感到非常困惑。

const int MIN_SIZE = 10000;
const int MAX_SIZE = 100000;

int main()
{
  for(j = MIN_SIZE; j <= MAX_SIZE; j += MIN_SIZE) {
    int *arrPtr = new int[j];
    for(int i = 0; i < j; i++)
       arrPtr[i] = 1; //When I put rand() here, it works fine but in any constant it gives stack overflow
    quickSort(arr, 0, j - 1);
    delete []arrPtr;
  }
}

上面的代码基本上创建了一个动态分配的数组，其大小为 j，每轮增加 MIN_SIZE(10,000)，并为每个索引分配一些特定的整数。分配后，它使用快速排序算法进行排序，我将在下面提供我的算法，然后在完成后释放该数组。这整个事情重复了 MAX_SIZE(100,000)。

这是我的快速排序代码：

void quickSort(int *arr, int front, int rear)
{
    if (front < rear)
    {
        int part = partition(arr, front, rear);
        quickSort(arr, front, part - 1);
        quickSort(arr, part + 1, rear);
    }
}

int partition(int *arr, int front, int rear)
{
    int element = arr[rear];
    int i = front - 1;
    for (int j = front; j<rear; ++j)
    {
        if (arr[j] <= element)
        {
            ++i;
            long temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    long temp = arr[i + 1];
    arr[i + 1] = arr[rear];
    arr[rear] = temp;
    return i + 1;
}

我正在尝试实现严格使用 最后一项作为主元 的快速排序算法。在这种情况下，我遇到了一个奇怪的问题：当我使用 rand() 函数将数组的每个值分配给一个随机数时，一切正常，但是，当我输入一个常量值时，数组上升到 4039（当您操作 MAX_SIZE 和 MIN_SIZE 时）然后给出 堆栈溢出 错误。我真的很困惑，为什么这会导致问题，此外，为什么是 4039？

Answer 1

使用最后一个元素作为枢轴元素的快速排序在以直接方式实现时预计会溢出相同元素的堆栈。这就是快速排序的工作原理。就是算法中的一个"defect"。

要了解原因，只需查看递归函数调用的创建方式。

quicksort(arr, 0, 100)  - will produce the recursive calls
   quicksort(arr, 0, 99); and
   quicksort(arr, 100, 100);

问题是 quicksort(arr, 0, 99); 将对数组中的每个元素进行递归。

在您的情况下，您的堆栈已满 4039 个元素。您似乎在每个调用中都有大约 8 个整数值的状态，这将提示您堆栈的最大大小。我猜大约 1 MB。

随机整数不是这种情况，因为递归调用的深度将在递归的左右部分之间均匀分布。这种期望的行为使得递归深度接近 log N。对于您的 MAX_SIZE，深度约为 17，而不是 100000。这就是快速排序被描述为 N log N 算法的原因。第一个 N 来自分区。

Answer 2

具有端点的常量数组并将数组一分为二导致递归深度 "number of elements in the array" 和 O(n^2) 时间。

有很多解决方法。

首先，将数组分成 3 个部分。大于、小于和等于进行分区。相等介于两者之间。这修复了你运行的极端情况。它增加了常数因子，但快速排序成本变为 O(n lg m)，其中 m 是作为奖励的不同元素的数量。

排序数组仍然死得很惨。做一个更好的分区选择器。随机分区使可怕行为的概率接近于 0。选择 3（或 2k+1）个元素（可能在运行dom）并使用它们的中位数是另一种方法。对于确定性的良好行为，在 O(n) 时间内找到 30% 和 70% 标记之间的元素的算法称为 "median of 5"（这不仅仅是取 5 个元素的中值）。

另一个技巧是对数组进行分区，在较小的分区上递归，在较大的分区上循环。这解决了递归深度问题，但没有解决运行时问题。

接下来，考虑小数组长度的转义策略。与选择排序相比，对（比如）8 个元素的快速排序可能严重次优。一旦你有了逃避策略，你就可以优化地使用快速而肮脏的快速排序（选择 3 运行dom 元素作为主元等）并跟踪递归深度。如果您传递 2*lg(n) 深度，请转义到可证明正确的快速排序（5 的中位数以找到枢轴）。当你下降到少于 8 个（调整这个）元素时，切换到选择排序。

最后，当您 std::sort 时，上述所有内容和更多内容可能已经完成。所以改用它。

Answer 3

如果您总是首先递归到较小的一半并且编译器为第二次调用生成尾递归，则可以保证 O(log(N)) 的堆栈深度。

void quickSort(int *arr, int front, int rear)
{
    if (front < rear)
    {
        int part = partition(arr, front, rear);
        int a, b, c, d;
        if (part - front <= rear - part)
        {
            a = front;
            b = part - 1;
            c = part + 1;
            d = rear;
        }
        else
        {
            a = part + 1;
            b = rear;
            c = front;
            d = part - 1;
        }
        quickSort(arr, a, b);
        quickSort(arr, c, d);
    }
}

Quicksort 给出常量而不是随机数的 stackoverflow

Quicksort gives stackoverflow on constant numbers but not on random numbers

c++

arrays

sorting

algorithm

quicksort