排序之直接插入排序和折半插入排序

朴灿烈づ我的快乐病毒、 2022-08-22 14:13 277阅读 0赞

直接插入排序和折半插入排序

#include <iostream>
    #include <cstdio>
    
    #define Maxsize 100
    
    using namespace std;
    
    typedef int KeyType;
    typedef char* InfoType;
    typedef struct
    {
        KeyType key;
        InfoType otherinfo;
    } RedType;
    typedef struct
    {
        RedType r[Maxsize];
        int length;
    } SeqList;
    
    void Create(SeqList &L)
    {
        cout<<"Please Input the Length of the SeqList:"<<endl;
        scanf("%d",&L.length);
        if(L.length==0)
            return;
        cout<<"Please Input the datas of the SeqList:"<<endl;
        for(int i=1; i<=L.length; i++)
        {
            scanf("%d",&L.r[i]);
            L.r[i].otherinfo=NULL;
        }
    }
    
    void OutPut(SeqList L)
    {
        cout<<"The SeqList is:"<<endl;
        for(int i=1; i<=L.length; i++)
        {
            cout<<L.r[i].key<<" ";
        }
        cout<<endl;
    }
    
    void InsertSort(SeqList &L)///直接插入排序
    {
        int i,j;
        for(i=2; i<=L.length; i++)
        {
            L.r[0]=L.r[i];
    //        for(j=i-1;L.r[0].key<L.r[j].key;j--)//方法一
    //        {
    //            L.r[j+1]=L.r[j];
    //        }
    //        L.r[j+1]=L.r[0];
    
    
            int j=i-1;///方法二
            while(L.r[j].key>L.r[0].key && j>=1)
            {
                L.r[j+1]=L.r[j];
                j--;
            }
            L.r[j+1]=L.r[0];
        }
    }
    
    void BiSertSort(SeqList &L)///折半插入排序
    {
        int low,high,mid,i,j;
        for(int i=2;i<=L.length;i++)
        {
            L.r[0]=L.r[i];
            low=1;
            high=i-1;
            while(low<=high)
            {
                mid=(low+high)/2;
                if(L.r[mid].key<L.r[0].key)
                {
                    low=mid+1;
                }
                else high=mid-1;
            }
            for(int k=i-1;k>=high+1;k--)
                L.r[k+1]=L.r[k];
            L.r[high+1]=L.r[0];
        }
    }
    
    int main()
    {
        SeqList L;
        Create(L);
        OutPut(L);
        InsertSort(L);
        OutPut(L);
        BiSertSort(L);
        OutPut(L);
        return 0;
    }