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

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”类型可能因操作系统而异。如果您认为 int 有问题，我建议只使用“long long”或更好的“size_t”。

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