c++ - 快速排序的 C++ 实现中的运行时错误

Question

我正在编写一个快速排序的实现来复习我的 C++ 技能，但是我遇到了一个让我很困惑的错误。该算法似乎在大约 25% 的时间内运行良好，但我在另外 75% 的时间内一直遇到错误，程序报告段错误或堆栈溢出。如果有人可以提供帮助，将不胜感激。提前致谢。

#include <iostream>
#include <string.h>
#include <ctime>
using namespace std;

#define size 20

void printSet(int* set);
int* quicksort(int* set, int l);
int* concat(int* less, int countL, int* greater, int countG);

int main()
{
    srand(time(NULL));
    int* set;
    set = new int[size];
    for(int i=0; i<size; i++)
        set[i]=rand()%200;
    printSet(set);
    set = quicksort(set, size);
    printSet(set);
    delete set;
    int i;
    cin>> i;
    return 0;
}

int* quicksort(int* set, int l)
{
    //cout<<"QS\n";
    if (l <= 1)
        return set;
    int*      less = new int[l];
    int*   greater = new int[l];
    int pivotIndex = rand() % l, 
          pivotVal = set[pivotIndex],
            countL = 0,
            countG = 0;

    for(int i=0; i<l; i++)
    {
        if (set[i] < pivotVal)
            less[countL++]=set[i];
        else
            greater[countG++]=set[i];
    }
    set = concat(quicksort(less, countL), countL, quicksort(greater, countG), countG);

    return set;
}

int* concat(int* less, int countL, int* greater, int countG)
{
    //cout<<"concat\n";
    int* set;
    set = new int[size];

    int i;

    for(i=0; i<countL; i++)
        set[i]=less[i];
    for(int j=0; j<countG; j++)
        set[i+j]=greater[j];

    return set;
}

void printSet(int* set)
{
    cout<<"******************\nPrinting Set\n";
    for(int i=0; i< size; i++)
    {
        cout<<i<<": "<<set[i]<<endl;
    }
}

Answer 1

我认为您的一个错误是在 main 的这一行中:

delete set;

这里的问题是set是一个用new[]分配的数组。要释放它的内存，您需要通过匹配调用 delete[] 来删除它。这可以通过将行重写为

来解决

delete[] set;

此外，在某些情况下，您的代码有机会无限递归。特别是，假设您尝试对包含 0 的两个拷贝的列表进行排序。在这种情况下，请考虑以下代码将执行的操作:

for(int i=0; i<l; i++)
{
    if (set[i] < pivotVal)
        less[countL++]=set[i];
    else
        greater[countG++]=set[i];
}
set = concat(quicksort(less, countL), countL, quicksort(greater, countG), countG);

由于您的主元是 0(这是唯一的选择!)，您将遍历数组并将数组中的两个 0 放入 greater。因此，当您在 greater 上递归调用 quicksort 时，您最终会递归地尝试对开始时完全相同的范围进行排序，从而导致无限递归。

要解决此问题，请尝试更新您的代码，以便将您分成三组 - 小于主元的元素、大于主元的元素和等于主元的元素。您仍然会在更小和更大的范围上递归，但您不会递归地在相等的值上调用自己。这将确保始终在比您开始时更小的范围内调用递归。

最后，正如其他人所指出的，您当前的实现泄漏了大量 内存，因为您从未释放任何您构造的临时数组。为避免这种情况，请考虑将原始数组的使用替换为 std::vector，它有自己的内存管理并且不会泄漏任何内存。此外，它大大简化了将数组拆分为多个区域的过程，因为您只需使用 push_back 来追加元素。

希望这对您有所帮助!