qq_17642463
LawrenceR77
2017-03-26 11:48

学算法的时候写了个三路快排(C++),然后编译器又请我吃bug了,各位大佬麻烦帮我看看吧

  • 算法
  • c++
 /*-----------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条回答