Quicksort的C++实现中的运行时错误

Question

我正在写一个quicksort的实现来提高我的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

我相信你的一个错误就在这一行中:

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);

由于您的pivot元素为0(这是唯一的选择!),您将遍历数组并将数组中的两个0放入greater.因此,当您以递归方式调用quicksort时greater,您将最终递归尝试对与您开始时完全相同的范围进行排序,从而导致无限递归.

要解决此问题,请尝试更新代码,以便将其分为三组 - 小于枢轴的元素,大于枢轴的元素以及等于枢轴的元素.你仍会在越来越小的范围内递归,但你不会以相等的值递归地调用自己.这将确保始终在比您开始时更小的范围上调用递归.

最后,正如其他人所指出的那样,您当前的实现会泄漏大量内存,因为您永远不会释放您构造的任何临时数组.为避免这种情况,请考虑将原始数组的使用替换为std::vector自己的内存管理,并且不会泄漏任何内存.此外,它使得将阵列分割成区域变得非常容易,因为您可以使用它push_back来附加元素.

希望这可以帮助!