直接插入排序、希尔排序、快速排序、堆排序算法比较-蒲公英云

直接插入排序、希尔排序、快速排序、堆排序算法比较

进行典型内部排序算法的比较，随机产生整数样本，进行四种排序，并比较各种排序算法的执行时间。

#include "stdio.h"
#include "stdlib.h" 
#include "conio.h"
#include "time.h"
#define MAXSIZE 20
typedef struct{
    int key;
}RedType;
typedef struct{            //定义顺序表的存储结构 
    RedType *r;            //存储空间基址，r[0]闲置或用作哨兵或用作缓冲区/
    int length;            //顺序表的长度 
}SqList;
void InitSqList(SqList *L){
    L->r=(RedType *)malloc((MAXSIZE+1)*sizeof(RedType));
    L->length=0;
}//InitSqList
void CreateSqList(SqList *L){//输入数据元素个数，随机产生整数样本 
    int i;
    srand((unsigned)time(0));
    printf("\n请输入顺序表的长度: ");
    scanf("%d",&L->length);
    for ( i=1; i<=L->length; i++){
        L->r[i].key=rand()%100;//随机产生整数样本
    }
    printf("\n\n未排序的数据为:\n");
    for( i=1; i<=L->length; i++)
        printf("%8d",L->r[i]);
}//CreateSqList
/*************************************直接插入排序********************************************/ 
void InsertSort(SqList *L){//直接插入排序 
    int i,j;
    if(!L->length){
        printf("该顺序表为空!");
    }
    for(i=2; i<=L->length; i++)
        if(L->r[i].key < L->r[i-1].key){
            L->r[0].key=L->r[i].key;//复制哨兵
            for(j=i-1; L->r[0].key<L->r[j].key; j--){
                L->r[j+1].key=L->r[j].key;//元素后移 
            }//for
            L->r[j+1].key = L->r[0].key;//元素插入 
        }//if
}//InsertSort
/*************************************希尔排序********************************************/ 
void shellSort(SqList *L,int dk){//希尔排序
    int i,j; 
    for(i=dk+1; i<=L->length; i++)
        if(L->r[i].key < L->r[i-1].key){
             L->r[0].key=L->r[i].key;//复制哨兵
             for(j=i-dk; j>0&&L->r[0].key<L->r[j].key; j-=dk)
                 L->r[j+dk].key = L->r[j].key;//元素后移 
             L->r[j+dk].key = L->r[0].key;//元素插入
         }//if
} //shellSort
void shellInsert(SqList *L){
    int dk;
    for(dk=L->length; dk>0; dk=dk/2){
        shellSort(L,dk);//每次的增量都为dk/2,最终变为1 
    }                    //当dk变为1是就是最基本的直接插入排序 
}//shellSqList
/*************************************快速排序********************************************/ 
int Partition(SqList *L, int low, int high){
    int pivotkey; 
    L->r[0].key = L->r[low].key;
    pivotkey = L->r[low].key;
    while(low<high){
        while(low<high && L->r[high].key >= pivotkey) --high;
        L->r[low].key = L->r[high].key;
        while(low<high && L->r[low].key <= pivotkey) ++low;
        L->r[high].key = L->r[low].key;
    }//while
    //当low=high时跳出循环 
    L->r[low].key = L->r[0].key; 
    return low;
}//Partition
void  QSort(SqList *L, int low, int high){//递归快速排序 
    int pivotloc;
    if(low<high){
        pivotloc = Partition(L, low, high);
        QSort(L, low, pivotloc-1);
        QSort(L, pivotloc+1, high);
    }
}//QSort
/*************************************堆排序********************************************/
void HeapAdjust(SqList *L, int s, int m){
    int j,rc;
    rc = L->r[s].key;
    for(j=2*s; j<=m; j*=2){
        if(j<m && L->r[j].key < L->r[j+1].key) ++j;
        if(rc > L->r[j].key) break;
        L->r[s].key = L->r[j].key;
        s = j;
    }
    L->r[s].key = rc; 
}//HeapAdjust
void HeapSort(SqList *L){
    int i,temp;
    for (i=L->length/2; i>0; i--)
        HeapAdjust(L,i,L->length);
    for (i=L->length; i>1; i--){
        temp = L->r[1].key;
        L->r[1].key = L->r[i].key;
        L->r[i].key = temp;
        HeapAdjust(L,1,i-1);
    }
}//HeapSort
/*************************************输出函数********************************************/ 
void outputSqList(SqList *L){//输出排序之后的元素 
    int i;
    printf("\n该顺序表的长度为：:%d\n",L->length);
    printf("\n\n排序了的数据为 : \n");
    for(i=1; i<=L->length; i++){
        printf("%8d",L->r[i].key);
    }
    printf("\n");
}//outputSqList
/*************************************复制链表函数********************************************/ 
void CopySqList(SqList *L, SqList *L_COPY){
    int i;
    if ( !L->length ){
        printf("该顺序表为空！\n");
    }
    else{
        for (i=1; i<=L->length; i++)
            L_COPY->r[i].key = L->r[i].key;
        L_COPY->length = L->length;
    }
}//CopySqList
int main(){
    SqList L, L_COPY;//L为初始顺序表 ,L_COPY为L的副本，用于排序
    clock_t start,finish;
    int select,flag;//用户输入的选项 
    flag = 1;
    InitSqList(&L);
    InitSqList(&L_COPY);
    CreateSqList(&L);
    while(flag){
        //mnum=0;cnum=0;
        CopySqList(&L,&L_COPY);
        printf("\n请输入选:\n1. 直接插入排序\n2. 希尔排序\n3. 快速排序\n4. 堆排序\n5.退出\n");
        scanf("%d",&select);
        switch(select){
            case 1:
                start=clock();
                InsertSort(&L_COPY);
                finish=clock();
                break;
            case 2:
                start=clock();
                shellInsert(&L_COPY);
                finish=clock();
                break;
            case 3:
                start=clock();
                QSort(&L_COPY,1,L.length);
                finish=clock();
                break;
            case 4:
                start=clock();
                HeapSort(&L_COPY);
                finish=clock();
                break;
            case 5:
                flag=0;
                exit(0);
        }
        outputSqList(&L_COPY);
        //printf("\n排序花的时间 : %lf Seconds\n",double(finish-start));
    }
    return 0;
}

最后对，这些排序算法的复杂度进行一下简单的比较

算法种类	时间复杂度			空间复杂度	是否稳定
最好情况	平均情况	最坏情况
直接插入排序	O(n)	O(n²)	O(n²)	O(1)	是
希尔排序				O(1)	否
快速排序	O(nlog₂n)	O(nlog₂n)	O(n²)	O(log₂n)	否
堆排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(1)	否