SWUST软件技术基础实验（4）排序算法的实现

妖狐艹你老母 2021-09-23 12:06 233阅读 0赞

1.实验目的：  
掌握直接插入排序、希尔排序、快速排序算法的实现。  
2.实验内容：  
对于给定的某无序序列，分别用直接插入排序、希尔排序、快速排序等方法进行排序，并输出每种排序下的各趟排序结果。  
各排序算法输入的无序序列：26 5 37 1 61 11 59 15 48 19  
3.实验要求：  
编程实现直接插入排序、希尔排序、快速排序各算法函数，并编写主函数对各排序函数进行测试。  
修改：在直接插入排序函数中的for循环将i<=s修改为了i<s

#include<iostream>
    #include<ctime>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int s=11;
    typedef char datatype;
    typedef struct
    { 
        int key;
        datatype others;//记录的其他域
    } rectype;
    /*插入排序*/
    void InsertSort(rectype R[])
    { 
        int i,j;
        for(i=2; i<s; i++)//插入的数据分别在1到n当中
        { 
            memcpy(&R[0],&R[i],sizeof(rectype));
            j=i-1;
            while(R[0].key<R[j].key)
            { 
                R[j+1]=R[j];//将关键字大于R[i].key 记录后移
                j--;
            }
            R[j+1]=R[0];
        }
    }
    /*希尔排序*/
    void ShellSort(rectype R[],int n)
    { 
        int i,j,h;
        rectype temp;
        h=n/2;
        while(h>0)
        { 
            for(j=h; j<=n-1; j++)
            { 
                temp=R[j];
                i=j-h;
                while((i>=0)&&temp.key<R[i].key)
                { 
                    R[i+h]=R[i];
                    i=i-h;
                }
                R[i+h]=temp;
    
            }
            h/=2;//增量为1排序后终止算法
        }
    
    }
    int Partition(rectype R[],int l,int h)
    { 
        int i,j;
        rectype temp;
        i=l;
        j=h;
        temp=R[i];//快排第一次的基准
        int flag=1;//修改flag
        while(flag)
        { 
            while((R[j].key>=temp.key)&&(i<j))
                j--;
            if(i<j)
                R[i++]=R[j];
            while((R[i].key<temp.key)&&(i<j))
                i++;
            if(i<j)
                R[j--]=R[i];
            if(i==j)
                flag=0;
        }//这段可以结合快排算法结合理解
        R[i]=temp;
        return i;
    }
    void QuickSort(rectype R[],int s1,int t1)
    { 
        int i;
        if(s1<t1)
        { 
            i=Partition(R,s1,t1);//对R[s1]~R[t1]作划分
            QuickSort(R,s1,i-1);
            QuickSort(R,i+1,t1);
        }
    }
    int main()
    { 
        // /t的含义是跳格
        rectype R[s];
        int i;
        /*插入测试*/
        printf("请输入使用插入算法排序的10个数据\n");
        for(i=1; i<s; i++)
        { 
            scanf("%d",&R[i].key);
        }
        printf("插入排序之前\n");
        for(i=1; i<s; i++)
        { 
            printf("%d\t",R[i].key);
        }
        InsertSort(R);
        printf("\n插入排序之后\n");
        for(i=1; i<s; i++)
        { 
            printf("%d\t",R[i].key);
        }
        /*希尔测试*/
        printf("\n请输入使用希尔算法排序的10个数据\n");
        for(i=0; i<s-1; i++)
        { 
            scanf("%d",&R[i].key);
        }
        printf("\n希尔排序之前\n");
        for(i=0; i<s-1; i++)
        { 
            printf("%d\t",R[i].key);
        }
        ShellSort(R,10);
        printf("\n希尔排序之后\n");
        for(i=0; i<s-1; i++)
        { 
            printf("%d\t",R[i].key);
        }
        /*快排测试*/
        printf("\n请输入使用快排算法排序的10个数据\n");
        for(i=1; i<s; i++)
        { 
            scanf("%d",&R[i].key);
        }
        printf("\n快排排序之前\n");
        for(i=1; i<s; i++)
        { 
            printf("%d\t",R[i].key);
        }
        QuickSort(R,1,10);
        printf("\n快排排序之后\n");
        for(i=1; i<s; i++)
        { 
            printf("%d\t",R[i].key);
        }
    }
    //26 5 37 1 61 11 59 15 48 19