学算法的时候写了个三路快排(C++),然后编译器又请我吃bug了,各位大佬麻烦帮我看看吧
 /*-----------Quick Sort 3 Ways-----------*/
template<typename T>
void QuickSort3ways(T arr[], int n)
{
    srand(NULL);
    Sub_QuickSort3ways(arr, 0, n - 1);
}

template<typename T>
void Sub_QuickSort3ways(T arr[], int L, int R)
{
    swap(arr[L], arr[rand() % (R - L + 1) + L]);
    T v = arr[L];

    int lt = L;
    int gt = R + 1;
    int i = L + 1;
    while (i < gt)
    {
        if (arr[i] < v)
        {
            swap(arr[i], arr[lt + 1]);
            lt++;
            i++;
        }
        else if (arr[i] > v)
        {
            swap(arr[i], arr[gt - 1]);
            gt--;
        }
        else
            i++;
    }

    swap(arr[L], arr[lt]);

    Sub_QuickSort3ways(arr, L, lt - 1);
    Sub_QuickSort3ways(arr, gt, R);
}
 int main()
{
    int n = 100000;
    int *arr1 = GenerateRandomArray(n, 0, n);

    TimeTest("Quick Sort 3 Ways", QuickSort3ways, arr1, n);
    delete[] arr1;

    system("pause");

    return 0;
}

先解释一把:GenerateRandomArray 生成一个随机数组,参数是元素个数,和元素的范围,函数内部用的是new申请的内存。
Time Test 测试算法的运行时间,参数分别是:算法名,使用的函数,数组和元素个数。
编译器:VS2015

然后他就告诉我栈溢出了

图片说明

然后我找到了 call stack模块,里面是这样的:
图片说明

有点蒙,为啥总是说R的值为-1??是不是哪里又写错了……

为什么没有人

1个回答

template<typename T>
void QuickSort3ways(T arr[], int n)
{
    srand(NULL);
    Sub_QuickSort3ways(arr, 0, n - 1);
}

template<typename T>
void Sub_QuickSort3ways(T arr[], int L, int R)
{
    if (R <= L)
    {
        return;
    }
    swap(arr[L], arr[rand() % (R - L + 1) + L]);
    T v = arr[L];

    int lt = L;
    int gt = R + 1;
    int i = L + 1;
    while (i < gt)
    {
        if (arr[i] < v)
        {
            swap(arr[i], arr[lt + 1]);
            lt++;
            i++;
        }
        else if (arr[i] > v)
        {
            swap(arr[i], arr[gt - 1]);
            gt--;
        }
        else
            i++;
    }

    swap(arr[L], arr[lt]);

    Sub_QuickSort3ways(arr, L, lt - 1);
    Sub_QuickSort3ways(arr, gt, R);
}

int * GenerateRandomArray(int n, int n1, int n2)
{
    int *pArr = new int[n];
    for (int i = 0;i < n;i ++)
    {
        pArr[i] = (rand() % n2);
    }
    return pArr;
}

int main()
{
    int n = 10;
    int *arr1 = GenerateRandomArray(n, 0, n);

    //TimeTest("Quick Sort 3 Ways", QuickSort3ways, arr1, n);
    QuickSort3ways(arr1,n);
    delete[] arr1;

    system("pause");

    return 0;
} 
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问