我的快速排序在已排序的数据上崩溃

我想检查数组中不同数据的性能时间（随机，已排序，按降序排序）。我的快速排序在已排序的数据上崩溃

void Quicksort(int *T, int Lo, int Hi) 
{ 
    if (Lo<Hi){ 
     int x=T[Lo]; 
     int i=Lo, j=Hi; 
    do 
    { 
     while (T[i] < x) ++i; 
     while (T[j] > x) --j; 
     if (i<=j) 
     { 
     int tmp = T[i]; 
     T[i] = T[j]; 
     T[j] = tmp; 
     ++i; --j; 
     } 
    } while(i < j); 
    if (Lo < j) Quicksort(T, Lo, j); 
    if (Hi > i) Quicksort(T, i, Hi); 
    } 
}

下面是用于生成并填写测试阵列功能：

int* createArr(int length){ 
    int* Arr= new int[length]; 
    return Arr; 
    } 

void Random(int *A, int length){ 
     for (int i=0;i<length;i++){ 
     A[i]=rand(); 
    } 
} 
void Order(int *A, int length){ 
     for (int i=0;i<length;i++){ 
     A[i]=i; 
    } 
} 

void Backwards(int *A, int length){ 
     for (int i=0;i<length;i++){ 
     A[i]=length-i; 
    } 
}

它工作正常的随机数，但是当我尝试以填补它按升序排列，排序，它崩溃堆栈溢出。任何人都可以给我提示为什么会发生这种情况？

来源

2014-04-03 user3365101

看起来像有序desc阵列是这种算法的最坏情况，你可能在非常大的阵列上运行它，所以你的函数调用自己很多次，以至于你正在运行到堆栈溢出。检查您的操作系统和编译器文档，了解调用堆栈的限制。为了解决这个问题，你可以考虑用循环替换递归。 – AlexanderM

@AlexanderM有序的desc数组实际上是选择第一个（或最后一个）项作为支点的算法的最坏情况。选择中心项目平均效果更好 - 不太可能经常在阵列中心找到最小或最大的项目。更好的是探测三个位置并选择三者的中位数作为关键点。 – CiaPan

当您选择[Lo]项作为分区值（数据透视表）并且该数组已经排序时，则会得到一个分区1（长度为1）。这会导致数组较长部分的下一个（递归）调用只处理一个小于上一个级别的项目。因此，正如@AlexanderM指出的那样，您将深入到数组长度的递归中。如果数组很大，几乎肯定会导致堆栈溢出。

尝试使用尾部消退：检查哪个部分更短，并使用resursive调用对其进行排序，然后继续使用较长部分的当前级别。要做到这一点与while替换第一个if并更换

if (Lo < j) Quicksort(T, Lo, j); 
if (Hi > i) Quicksort(T, i, Hi);

与

if (j-Lo < Hi-i) 
{ 
    Quicksort(T, Lo, j); 
    Lo = i; 
} 
else 
{ 
    Quicksort(T, i, Hi); 
    Hi = j; 
}

这不会使程序得更快 - 它仍然需要在为O（n^2）时间已经排序的数组，但是会防止线性堆栈内存使用，保持最坏的O（log n）。

有关更好性能的更多方向，请参阅维基百科文章Quicksort，部分选择枢轴。

来源

2014-04-04 21:10:40 CiaPan

我的快速排序在已排序的数据上崩溃

回答

相关问题