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

Question

一万数据量的时候

十万数据量的时候

代码：
#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;

}

Answer 1

liuyubobobo 2019-01-24 02:18:17

课程中介绍了，对于近乎有序的数据，不加随机化的快排将退化成为O(n^2)的算法。50000的数据量，对于O(n^2)的算法，一时半会儿是计算不完的。

如果你足够有耐心的话，再多等一等，现代计算机在1个小时内应该能完成：）

这就是我们要引随机选择pivot的原因啊！再回顾一下1:40的实验，就是再说这个问题啊！：）

继续加油！：）

• 提问者 慕UI4716311 #1

  可是我的dev直接就停止了啊，显示的返回值和我上次希尔排序数据量超过50万超出栈的范围一样

• liuyubobobo 回复 提问者 慕UI4716311 #2

  哦！对！由于对于近乎有序的数组，没有随机化的快速排序每次的分割近乎都是0和n-1，是的递归深度近乎就是n。当n过大的时候，会由于递归深度过高导致栈溢出！：）

• 提问者 慕UI4716311 回复 liuyubobobo #3

  好的，谢谢您