为什么我的快速排序对近乎有序的数据在50000以后无法输出结果，但是对无序数组到1千万也正常运行，如果是栈大小的问题，我感觉不应该会有这种问题啊？

来源：3-6 随机化快速排序法

慕UI4716311

2019-01-23

图片描述
一万数据量的时候

十万数据量的时候

代码：
#include
#include

#include"SortTestHelper.h"
#include"MergeSort.h"
#include"InsertionSort.h"

using namespace std;

template
int Partition(T arr[],int l,int r) {
int aux=arr[l];
int i,j=l;
for(i=l+1; i<=r; i++) {
if(arr[i]<aux){
j++;
swap(arr[j],arr[i]);

	}

}
swap(arr[l],arr[j]);
return j;

}
template
void __QuickSort(T arr[],int l,int r) {
if(r-l<=15) {
BetterInsertionSort(arr,l,r);
return; //判断递归终止的条件
}
int p=Partition(arr,l,r);
__QuickSort(arr,l,p-1);
__QuickSort(arr,p+1,r);
}

template
void QuickSort(T arr[],int n) {
__QuickSort(arr,0,n-1);
}

int main() {
int n=100000;
int *arr=SortTestHelper::generateArray(n,0,n);
int *arr1=SortTestHelper::generateNearlyOrderedArray(n,100);

SortTestHelper::testSort("QuickSort",QuickSort,arr,n);
SortTestHelper::testSort("NearlyOrderedQuickSort",QuickSort,arr1,n);

delete[] arr;
delete[] arr1;
return 0;

}

写回答

1回答