数据结构C语言版之插入排序（直接插入排序和折半插入排序）

迈不过友情╰ 2022-04-13 03:16 207阅读 0赞

就这两种插入排序的定义等等就忽略了，不懂自行百度。

直接插入排序正序时最好时间复杂度O(n),逆序最坏O(n2),平均O(n2)，空间复杂度O(1)；稳定；原始序列基本有序时该方法好

折半插入排序逆序最坏O(n2),正序时O(NLogN) , S(n)=O(1);稳定

主要提供代码。

直接插入排序的动态实现方法可以去B站上找找，有个动态演示的视频。

/*
            直接插入排序和折半插入排序
    */
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define MAXSIZE 20
    
    typedef struct{
        int elem[MAXSIZE+1];
        int Length;
    }SqList;
    
    void CreateSqList(SqList &L);// 初始化的声明
    void InsertSort(SqList &L);  // 直接插入排序的声明
    void putSqList(SqList &L);   // 输出的声明
    void BInsertSort(SqList &L); //折半插入排序的声明
    
    
    int main(){
        SqList L;
        int i;
        CreateSqList(L);
        printf("请选择进行排序的算法：\n");
        printf("1 代表 直接插入排序\n2 代表 折半插入排序\n请选择：\n");
        int cases;
        scanf("%d",&cases);
        if(cases == 2){
            BInsertSort(L);
            putSqList(L);
        }
        else if(cases == 1){
            InsertSort(L);
            putSqList(L);
        }
        else{
            printf("输入错误，无法排序");
        }
    }
    
    
    //     初始化SqList
    void CreateSqList(SqList &L){
        printf("请输入要排序的数字个数（不要超过%d个）\n",MAXSIZE);
        int num;    //排序数字的总数
        scanf("%d",&num);
        printf("请输入要排序的数字：\n");
        int i;
        for(i = 1; i <= num; i++){
            int tmp;  //临时数字
            scanf("%d",&tmp);
            L.elem[i] = tmp;
        }
        L.Length = num;
    }
    //    直接插入排序
    void InsertSort(SqList &L){
        int i,j;
        for(i = 2; i <= L.Length; i++){
            if(L.elem[i] < L.elem[i-1]){
                L.elem[0] = L.elem[i];
                L.elem[i] = L.elem[i-1];
                for(j = i - 2; L.elem[j] > L.elem[j-1]; j--){
                    L.elem[j+1] = L.elem[j];
                }
                L.elem[j+1] = L.elem[0];
            }
        }
    }
    //     折半插入排序
    void BInsertSort(SqList &L){
        int i,j;
        for(i = 2; i < L.Length; i++){
            L.elem[0] = L.elem[i];
            int low = 1, high =  i - 1;
            while(low <= high){
                int mid = (low+high)/2;
                if(L.elem[mid] > L.elem[0]) high = mid-1;
                else low = mid+1;
            }
            for(j = i-1; j >= high+1;j--){
                L.elem[j+1] = L.elem[j];
            }
            L.elem[high+1] = L.elem[0];
        }
    }
    //     输出
    void putSqList(SqList &L){
        int i;
        printf("输出的结果是：\n");
        for(i = 1; i <= L.Length;i++){
            printf("%d ",L.elem[i]);
        }
    }