当我使用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).

这是我的Quicksort代码：

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？

解决方法:

当以直接方式实现时,期望使用最后一个元素作为枢轴元素的快速排序会使堆栈溢出相同的元素.这就是quicksort的工作原理.这是算法中的“缺陷”.

要了解为什么只看一下如何创建递归函数调用.

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

问题是快速排序(arr,0,99);将递归数组中的每个元素.

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

随机整数的情况并非如此,因为递归调用的深度将均匀地分布在递归的左侧和右侧部分之间.这种期望的行为使得递归深度方法记录为N.对于MAX_SIZE,这是大约17的深度,而不是100000.这就是将快速排序描述为N log N算法的原因.第一个N来自分区.