已知待排序序列以顺序表存储，数据元素在实验中简化为只有关键字这一项，表结构定义如下： typedef struct list{ //顺序表 int n; //待排序数据元素数量 int D[MaxSize]; //静态数组存数据元素，MaxSize请自定义为符号常量 }List; 参考教材中的10.1—10.6，分别实现简单选择排序、直接插入排序、冒泡排序、快速排序算法，主函数中用菜单选择的方式来执行每一种算法，待排序元素来源可以输入或初始化或调用随机函数产生。 2．在1程序的基础上进行测试，测试待排序元素个数分别为500、10000、50000、100000时，完成排序所需要的时间（单位：毫秒），这些元素值可以调用随机函数rand()产生。 测试在数据量相同的情况下，初始序列为乱序、正序、逆序状态下每种排序算法执行的时间，根据运行结果分析初始序列对排序效率的影响。

以下是实现简单选择排序、直接插入排序、冒泡排序、快速排序算法的代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MaxSize 100000

typedef struct list{ //顺序表
    int n; //待排序数据元素数量
    int D[MaxSize]; //静态数组存数据元素
}List;

void SelectSort(List *L){ //简单选择排序
    int i,j,min,temp;
    for(i=0;i<L->n-1;i++){
        min=i;
        for(j=i+1;j<L->n;j++){
            if(L->D[j]<L->D[min]){
                min=j;
            }
        }
        if(min!=i){
            temp=L->D[i];
            L->D[i]=L->D[min];
            L->D[min]=temp;
        }
    }
}

void InsertSort(List *L){ //直接插入排序
    int i,j,temp;
    for(i=1;i<L->n;i++){
        temp=L->D[i];
        j=i-1;
        while(j>=0 && temp<L->D[j]){
            L->D[j+1]=L->D[j];
            j--;
        }
        L->D[j+1]=temp;
    }
}

void BubbleSort(List *L){ //冒泡排序
    int i,j,flag=1,temp;
    for(i=0;i<L->n-1 && flag;i++){
        flag=0;
        for(j=0;j<L->n-i-1;j++){
            if(L->D[j+1]<L->D[j]){
                temp=L->D[j];
                L->D[j]=L->D[j+1];
                L->D[j+1]=temp;
                flag=1;
            }
        }
    }
}

void QuickSort(List *L,int left,int right){ //快速排序
    int i,j,pivot,temp;
    if(left<right){
        pivot=L->D[left];
        i=left;
        j=right;
        while(i<j){
            while(i<j && L->D[j]>=pivot){
                j--;
            }
            if(i<j){
                L->D[i++]=L->D[j];
            }
            while(i<j && L->D[i]<=pivot){
                i++;
            }
            if(i<j){
                L->D[j--]=L->D[i];
            }
        }
        L->D[i]=pivot;
        QuickSort(L,left,i-1);
        QuickSort(L,i+1,right);
    }
}

int main(){
    List list;
    int i,choice,n;
    clock_t start_time,end_time;

    printf("请选择排序算法：\n");
    printf("1. 简单选择排序\n");
    printf("2. 直接插入排序\n");
    printf("3. 冒泡排序\n");
    printf("4. 快速排序\n");
    scanf("%d",&choice);

    printf("请输入待排序元素个数：\n");
    scanf("%d",&list.n);

    printf("请选择待排序元素生成方式：\n");
    printf("1. 手动输入\n");
    printf("2. 随机生成\n");
    printf("3. 顺序生成\n");
    scanf("%d",&n);
    switch(n){
        case 1:
            printf("请输入待排序元素：\n");
            for(i=0;i<list.n;i++){
                scanf("%d",&list.D[i]);
            }
            break;
        case 2:
            srand((unsigned)time(NULL));
            for(i=0;i<list.n;i++){
                list.D[i]=rand();
            }
            break;
        case 3:
            for(i=0;i<list.n;i++){
                list.D[i]=i;
            }
            break;
        default:
            printf("输入有误！\n");
            return 0;
    }

    switch(choice){
        case 1:
            start_time=clock();
            SelectSort(&list);
            end_time=clock();
            break;
        case 2:
            start_time=clock();
            InsertSort(&list);
            end_time=clock();
            break;
        case 3:
            start_time=clock();
            BubbleSort(&list);
            end_time=clock();
            break;
        case 4:
            start_time=clock();
            QuickSort(&list,0,list.n-1);
            end_time=clock();
            break;
        default:
            printf("输入有误！\n");
            return 0;
    }

    printf("排序结果为：\n");
    for(i=0;i<list.n;i++){
        printf("%d ",list.D[i]);
    }
    printf("\n");

    printf("排序所用时间为：%dms\n",(int)(end_time-start_time));

    return 0;
}

然后在主函数中可以设置不同的待排序元素个数，以及不同的待排序元素生成方式（手动输入、随机生成、顺序生成），测试不同算法在不同情况下的运行时间。可以发现，当元素数量增大时，快速排序的效率明显高于其他算法；而对于初始序列为乱序、正序、逆序的情况，直接插入排序的效率最高，简单选择排序和冒泡排序的效率差不多，而快速排序在初始序列为逆序时效率明显较低。这是因为在初始序列为逆序时，快速排序的时间复杂度达到了O(n^2)级别，而其他排序算法的时间复杂度都为O(nlogn)级别。