C++中的快速排序实现（测试失败）

问题描述：

我已经给出了一个在C++中实现Quicksort的任务，并且我已经成功编写了似乎可行的代码。当我测试我的失败算法时，当我用一百万个元素对二进制文件进行排序时，它崩溃了。请注意，我有两个文件，每个文件有一百万个元素。其中一个是未排序的，另一个是“几乎排序”的，而我的算法似乎只在对“几乎排序”文件进行排序时失败。这里是我的代码如下所示：C++中的快速排序实现（测试失败）

int partition(int arr[], int low, int high) 
{ 
    int pivotI = low; //pivot index 
    int pivot = arr[pivotI]; 
    int temp = arr[low]; 
    arr[low] = pivot; 
    arr[pivotI] = temp; 
    int partitionI = low; 
    low++; 
    while (low <= high) 
    { 
     if (arr[low] >= pivot) 
     { 
      if (arr[high] <= pivot) 
      { 
       temp = arr[high]; 
       arr[high] = arr[low]; 
       arr[low] = temp; 
       low++; 
      } 
      high--; 
     } 
     else if (arr[high] <= pivot) 
     { 
      low++; 
     } 
     else 
     { 
      low++; 
      high--; 
     } 
    } 
    if (low == high) 
    { 
     if (arr[low - 1] < pivot) 
     { 
      temp = arr[low]; 
     } 
     else 
     { 
      temp = arr[low - 1]; 
     } 
    } 
    else 
    { 
     temp = arr[high]; 
    } 
    arr[high] = arr[partitionI]; 
    arr[partitionI] = temp; 
    return high; 
} 

void quickSort(int arr[], int left, int right) 
{ 
    if (left < right) 
    { 
     int p = partition(arr, left, right); 
     quickSort(arr, left, p); 
     quickSort(arr, p + 1, right); 
    } 
}

*我得到一个堆栈溢出错误，当我跑说：“几乎排序”二进制文件。任何想法为什么发生这种情况？谢谢

解决此类问题的正确工具是您的调试器。在*堆栈溢出问题之前，您应该逐行执行您的代码。如需更多帮助，请阅读[如何调试小程序（由Eric Lippert撰写）]（https://ericlippert.com/2014/03/05/how-to-debug-small-programs/）。至少，您应该\编辑您的问题，以包含一个[最小，完整和可验证]（http://stackoverflow.com/help/mcve）示例，该示例再现了您的问题，以及您在调试器。 –

最可能太深的递归。 –

答

如果在快速排序中使用第一个值作为pivot值，那么已经排序好的列表是最糟糕的情况，因为pivot将始终是分区中的最低值。这可以大大增加递归深度。每次递归调用都需要在栈帧上有空间（由参数，局部变量和返回地址组成）。对于几百万个数字的排序列表，您可能需要一次激活近百万个堆栈帧。这很容易耗尽可用的堆栈空间并产生错误。

你可以尝试一种不同的数据透视算法来解决这个问题，比如三位数的中位数。

另一种解决方案可能不是使用递归，而是使用'std :: stack'。 –

您可以将中间元素用作中心元素，例如pivotI =（low + high）/ 2; – Trifon

答

避免堆栈溢出的一种方法是使用循环和递归的组合。在每个分区（）之后的quicksort（）中，检查是否（p - 左）< =（right-p-1），并且只对较小的部分使用递归，然后循环返回来分割较大的部分。这将最坏情况堆栈开销限制为log2（n）。但最坏情况下的时间复杂度仍然在O（n^2）。

最坏情况下的时间复杂度可以降低至O使用中位数的中值（正的log（n））

http://en.wikipedia.org/wiki/Median_of_medians

但所述恒定因子因子越大，减慢快速排序对于普通和最好的案例。

C++中的快速排序实现（测试失败）

相关推荐