我已经给出了一个在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)示例,该示例再现了您的问题,以及您在调试器。 –
最可能太深的递归。 –