检验快速排序及其改进算法时间效率问题

Question

其中正序逆序的时间效率均正确,乱序的部分就有错误.但是正序逆序及乱序的检验部分基本都是复制粘贴,随机数产生的地方好像也没有什么问题。但运行后只有乱序的改进算法比原算法的时间慢。跪求指导，哪一部分除了问题。
具体代码如下：

#include<iostream>
#include <ctime>
#include <stdlib.h>
#define Maxsize 20000

using namespace std;

typedef int KeyType;
typedef struct{
    KeyType key;
    int otherinfo;
}RedType;
typedef struct{
    RedType r[Maxsize+1];
    int length;
}sqList; 

int Random(int seed){
    return (25173*seed+13849)%32768;
}

void InsertSort(sqList &L){                      //直接插入排序 
    int i,j;
    for(i=2;i<=L.length;++i){
        if(L.r[i].key<L.r[i-1].key){            //将L.r[i]插入到有序子表 
            L.r[0]=L.r[i];                      //复制为哨兵 
            L.r[i]=L.r[i-1];
            for(j=i-2;L.r[0].key<L.r[j].key;--j)
                L.r[j+1]=L.r[j];                //记录后移 
            L.r[j+1]=L.r[0];                    //插入到正确位置 
        }
    }
}
int Partition(sqList &L,int low,int high){       //一趟快速排序 
    int pivotkey;
    L.r[0]=L.r[low];                             //用子表第一个记录做枢轴记录 
    pivotkey=L.r[low].key;                       //枢轴记录关键字 
    while(low<high){                             //从表的两端交替地向中间扫描 
        while(low<high&&L.r[high].key>=pivotkey) 
            --high;
        L.r[low]=L.r[high];                      //将比枢轴记录小的记录移到低端 
        while(low<high&&L.r[low].key<=pivotkey)
            ++low;
        L.r[high]=L.r[low];                      //将比枢轴记录大的记录移到高端 
    }
    L.r[low]=L.r[0];                             //枢轴记录到位 
    return low;                                  //返回枢轴位置 
}
void Quicksort(sqList &L,int low,int high){      //对子序列做快速排序 
    int pivotloc;
    if(low<high){
        pivotloc=Partition(L,low,high);
        Quicksort(L,low,pivotloc-1);
        Quicksort(L,pivotloc+1,high);
    }
}
void Quicksort1(sqList &L){                      //对L做快速排序 
    Quicksort(L,1,L.length);
} 
int partition(sqList &L,int low,int high){
    int mid,pivotkey;
    mid=(low+high)/2;

    //关键字取中值 
    if((L.r[low].key<L.r[mid].key&&L.r[mid].key<L.r[high].key)||(L.r[low].key>L.r[mid].key&&L.r[mid].key>L.r[high].key)){
        pivotkey=L.r[mid].key;
        L.r[mid]=L.r[low];
    }
    else if((L.r[low].key<L.r[high].key&&L.r[high].key<L.r[mid].key)||(L.r[low].key>L.r[high].key&&L.r[high].key>L.r[mid].key)){
        pivotkey=L.r[high].key;
        L.r[high]=L.r[low];
    }
    else{
        pivotkey=L.r[low].key;
    }
    while(low<high){                             
        while(low<high&&L.r[high].key>=pivotkey) 
            --high;
        L.r[low]=L.r[high];                      
        while(low<high&&L.r[low].key<=pivotkey)
            ++low;
        L.r[high]=L.r[low];                       
    }
    L.r[low].key=pivotkey;                            
    return low;       
} 
void quicksort(sqList &L,int low,int high){       
    int pivotloc;
    if(high-low>20){
        pivotloc=partition(L,low,high);
        quicksort(L,low,pivotloc-1);
        quicksort(L,pivotloc+1,high);
    }
    else if(high-low<=20)                           //待排子列长度小于20用直接插入排序 
        InsertSort(L);
}
void quicksort1(sqList &L){                       
    quicksort(L,1,L.length);
} 

int main(){
    int i;
    sqList L1,L2,L_up,L_down;
    float t_time;

    L1.length=Maxsize;
    L2.length=Maxsize;
    L_up.length=Maxsize;
    L_down.length=Maxsize;

    clock_t start;
    clock_t stop;
    srand(time(NULL));                               //设置随机数种子 

    for(i=1;i<=Maxsize;i++){                        //生成10000个随机数和两个相同的乱序待排序列 
        L1.r[i].key=Random(rand());
        L2.r[i]=L1.r[i];  
    } 
    for(i=1;i<=Maxsize;i++){                        //设置一个正序待排序列 
        L_up.r[i].key=2*i;  
    }   
    for(i=Maxsize;i>=1;i--){                        //设置一个逆序待排序列 
        L_down.r[Maxsize-i+1].key=2*i; 
    }

    cout << "现在开始验证各排序时间!~~" << endl << endl;

    start=clock();
    Quicksort1(L_up);
    stop=clock();
    t_time=(float)(stop-start)/CLOCKS_PER_SEC;
    cout << "1、正序->快速排序->时间为: " <<  t_time << "s" << endl << endl;

    start=clock();
    quicksort1(L_up);
    stop=clock();
    t_time=(float)(stop-start)/CLOCKS_PER_SEC;
    cout << "2、正序->快速排序(三者取中)->时间为:" << t_time << "s" << endl << endl;

    start=clock();
    Quicksort1(L_down);
    stop=clock();
    t_time=(float)(stop-start)/CLOCKS_PER_SEC;
    cout << "3、逆序->快速排序->时间为: " <<  t_time << "s" << endl << endl;

    start=clock();
    quicksort1(L_down);
    stop=clock();
    t_time=(float)(stop-start)/CLOCKS_PER_SEC;
    cout << "4、逆序->快速排序(三者取中)->时间为:" << t_time << "s" << endl << endl;

    start=clock();
    Quicksort1(L1);
    stop=clock();
    t_time=(float)(stop-start)/CLOCKS_PER_SEC;
    cout << "5、乱序->快速排序->时间为: " <<  t_time << "s" << endl << endl;

    start=clock();
    quicksort1(L2);
    stop=clock();
    t_time=(float)(stop-start)/CLOCKS_PER_SEC;
    cout << "6、乱序->快速排序(三者取中)->时间为:" << t_time << "s" << endl << endl; 

    cout << "由上,可以看出快速排序及其改进版的效率对比!" << endl;

    system("pause");
    return 0; 
} 

运行结果如下：

麻烦大家帮忙看看了。

Answer 1

为什么我执行你的程序Partition函数会在第1667次进入的时候报Stack overflow异常。