当处理数组中的大量数据时，算法会崩溃

Question

代码:

int* NewArr = CreateArray(size);
FillRandom(NewArr,size);
Quicksort(NewArr,0,size-1);

功能:

int* CreateArray(int length){
    int* arr= new int[length];
    return arr;
}
void FillRandom(int *array, int size){
   for (int i=0;i<size;i++){
      array[i]=rand()%20;
   }
}
void Quicksort (int* array, int left, int right){
   if(left<right)
   {
      int m=left;
      for(int i=left+1;i<=right;i++)
         if(array[i]<array[left])
            swap(array[++m],array[i]);
      swap(array[left],array[m]);
      Quicksort(array,left,m-1);
      Quicksort(array,m+1,right);
   }
}

该算法在30-50k的元素中工作良好。那么它就不能在100k上工作，因为堆栈溢出异常而崩溃。有人能告诉我为什么吗?我认为这是因为int限制，但它是32768，然而这段代码适用于50k个元素。

Answer 1

您可能已经达到了计算机上的最大堆栈大小，此外，根据您的操作系统，"int"类型可能有所不同。如果您认为整型存在问题，我建议您使用"long long"，或者更好的方法是使用"size_t"。

然而，根据手头的信息，您可能已经达到了最大堆栈大小。这可能是因为递归(每次保存一个新的左变量和右变量)，每一层都向下生成大量的堆栈变量。正如mellamokb已经提到的，您没有为快速排序正确地迭代，实际上您正在创建100k递归调用。

Answer 2

因为您只使用[0,20]范围内的数字，所以您将遇到具有所有相同数字的子数组。如果你有一个长度为K的子数组，那么处理这个子数组时的递归深度将是K，就像处理长度为K-1 K-2 K-3，等等的子数组一样。如果您从100,000个元素开始，那么您应该期望K的值在5,000范围内。这很可能导致堆栈溢出。尝试临时删除FillRandom中的% 20。

即使你没有堆栈溢出，你也会得到O(n^2)的运行时间。