数据结构实验六排序

今天药忘吃喽~ 2022-08-23 00:54 142阅读 0赞

数据结构实验六排序

背景知识：各种排序方法

目的要求

１．掌握常见的排序算法的思想及其适用条件。

２．掌握常见的排序算法的程序实现。

实验内容：

输入一组关键字序列分别实现下列排序:

1.实现简单选择排序、直接插入排序和冒泡排序。

2.实现希尔排序算法。

3.实现快速排序算法。

4.实现堆排序算法。

\*5.快速排序的非递归算法。

\*6.实现折半插入排序。

\*7.采用链式存储实现简单选择排序、直接插入排序和冒泡排序。

8.在主函数中设计一个简单的菜单，分别测试上述算法。

代码实现：

#include <iostream>
    #include <cstdio>
    
    #define Maxsize 100
    
    using namespace std;
    
    typedef int KeyType;
    typedef int InfoType;
    typedef struct
    {
        KeyType key;
        InfoType otherinfo;
    } RedType;
    typedef struct
    {
        RedType r[Maxsize+1];
        int length;
    } SqList;
    
    int dlta[Maxsize];
    
    void Create(SqList &L)
    {
        cout<<"Please Input the Length of List:"<<endl;
        scanf("%d",&L.length);
        cout<<"Please Input the Data of the List:"<<endl;
        for(int i=1; i<=L.length; i++)
        {
            scanf("%d",&L.r[i].key);
            L.r[i].otherinfo=0;
        }
    }
    
    void Output(SqList L)
    {
        cout<<"The List Is:"<<endl;
        for(int i=1; i<=L.length; i++)
        {
            cout<<L.r[i].key<<" ";
        }
        cout<<endl;
    }
    
    void Bubblf_sort(SqList &L)
    {
        RedType p;
        for(int i=1; i<=L.length; i++)
        {
            for(int j=i+1; j<=L.length; j++)
            {
                if(L.r[i].key>L.r[j].key)
                {
                    p=L.r[i];
                    L.r[i]=L.r[j];
                    L.r[j]=p;
                }
            }
        }
    }
    
    int SelectMinkey(SqList L,int i)
    {
        int k=i;
        RedType minn;
        minn=L.r[i];
        for(int j=i; j<=L.length; j++)
        {
            if(L.r[j].key<minn.key)
            {
                minn=L.r[j];
                k=j;
            }
        }
        return k;
    }
    
    void Select_sort(SqList &L)
    {
        RedType p;
        for(int i=1; i<=L.length; i++)
        {
            int j=SelectMinkey(L,i);
            if(i!=j)
            {
                p=L.r[i];
                L.r[i]=L.r[j];
                L.r[j]=p;
            }
        }
    
    }
    
    void ShellInsert(SqList &L,int dk)
    {
        int i,j;
        for(i=dk+1; i<=L.length; i++)
        {
            if(L.r[i].key<L.r[i-dk].key)
            {
                L.r[0]=L.r[i];
                for(j=i-dk; j>0&&(L.r[0].key<L.r[j].key); j-=dk)
                {
                    L.r[j+dk]=L.r[j];
                }
                L.r[j+dk]=L.r[0];
            }
        }
    }
    
    int DLTA(int dlta[],SqList L)
    {
        int k=L.length/2;
        int i=0;
        while(k>=1)
        {
            dlta[i++]=k;
            k/=2;
        }
        return i;
    }
    
    void Shell_sort(SqList &L,int dlta[],int t)
    {
        for(int k=0; k<t; k++)
        {
            ShellInsert(L,dlta[k]);
        }
    }
    
    int Partion(SqList &L,int low,int high)
    {
        int pivotkey;
        L.r[0]=L.r[low];
        pivotkey=L.r[low].key;
        while(low<high)
        {
            while(low<high && L.r[high].key>=pivotkey) --high;
            L.r[low]=L.r[high];
            while(low<high && L.r[low].key<=pivotkey) ++low;
            L.r[high]=L.r[low];
        }
        L.r[low]=L.r[0];
        return low;
    }
    void QSort(SqList &L,int low,int high)
    {
        int pivotloc=0;
        if(low<high)
        {
            pivotloc=Partion(L,low,high);
            QSort(L,low,pivotloc-1);
            QSort(L,pivotloc+1,high);
        }
    }
    void Quick_sort(SqList &L)
    {
        QSort(L,1,L.length);
    }
    
    typedef SqList HeapType;
    
    void HeapAdjust(HeapType &H,int s,int m)
    {
        RedType rc;
        rc=H.r[s];
        for(int j=2*s; j<=m; j*=2)
        {
            if(j<m && (H.r[j].key<H.r[j+1].key))
            {
                j++;
            }
            if(rc.key>=H.r[j].key) break;
            H.r[s]=H.r[j];
            s=j;
        }
        H.r[s]=rc;
    }
    
    void Heap_sort(HeapType &H)
    {
        RedType p;
        for(int i=H.length/2; i>0; --i)
            HeapAdjust(H,i,H.length);
        for(int i=H.length; i>1; --i)
        {
            p=H.r[1];
            H.r[1]=H.r[i];
            H.r[i]=p;
            HeapAdjust(H,1,i-1);
        }
    }
    
    void menu()
    {
        cout<<"Welcome to This World!"<<endl;
        cout<<"0.Exit."<<endl;
        cout<<"1.Create the List."<<endl;
        cout<<"2.Bubblf_sort."<<endl;
        cout<<"3.Select_sort."<<endl;
        cout<<"4.Shell_sort."<<endl;
        cout<<"5.Quick_sort."<<endl;
        cout<<"6.Heap_sort."<<endl;
    }
    
    int main()
    {
        SqList L;
        int casenum;
        int t;
        menu();
        cout<<"Please Input the Choose:"<<endl;
        while(cin>>casenum)
        {
            switch (casenum)
            {
            case 0:
                break;
            case 1:
                Create(L);
                Output(L);
                cout<<"Create Over!"<<endl;
                break;
            case 2:
                Bubblf_sort(L);
                Output(L);
                cout<<"Bubblf_sort Over!"<<endl;
                break;
            case 3:
                Select_sort(L);
                Output(L);
                cout<<"Select_sort Over!"<<endl;
                break;
            case 4:
                t=DLTA(dlta,L);
                Shell_sort(L,dlta,t);
                Output(L);
                cout<<"Shell_sort Over!"<<endl;
                break;
            case 5:
                Quick_sort(L);
                Output(L);
                cout<<"Quick_sort Over!"<<endl;
                break;
            case 6:
                Heap_sort(L);
                Output(L);
                cout<<"Heap_sort Over!"<<endl;
                break;
            }
            if(casenum==0)break;
        }
        return 0;
    }