- 学算法的时候写了个三路快排（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？？是不是哪里又写错了……
为什么没有人
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;
}
