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

╰+攻爆jí腚メ 2021-12-08 22:15 219阅读 0赞

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

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

#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;
    }

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

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td colspan="1">算法种类</td> 
   <td colspan="3">时间复杂度</td> 
   <td colspan="1">空间复杂度</td> 
   <td colspan="1">是否稳定</td> 
  </tr> 
  <tr> 
   <td>最好情况</td> 
   <td>平均情况</td> 
   <td>最坏情况</td> 
  </tr> 
  <tr> 
   <td>直接插入排序</td> 
   <td>O(n)</td> 
   <td>O(n²)</td> 
   <td>O(n²)</td> 
   <td>O(1)</td> 
   <td>是</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td colspan="3">&nbsp;</td> 
   <td>O(1)</td> 
   <td>否</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(nlog₂n)</td> 
   <td>O(nlog₂n)</td> 
   <td>O(n²)</td> 
   <td>O(log₂n)</td> 
   <td>否</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(nlog₂n)</td> 
   <td>O(nlog₂n)</td> 
   <td>O(nlog₂n)</td> 
   <td>O(1)</td> 
   <td>否</td> 
  </tr> 
 </tbody> 
</table>