六种排序算法(插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序)

爱被打了一巴掌 2022-04-05 03:14 265阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>
    #define MAX_NUM 32768
    
    typedef int ElemType;//元素类型
    typedef struct
    {
        ElemType key;
    } KeyType;//关键字的类型
    
    typedef struct
    {
        KeyType R[MAX_NUM+1];
        int length;
    }*orderList,Node;
    int compareTimes;//比较次数
    int moveTimes;//移动次数
    
    orderList init_orderList()
    {
        orderList l=(orderList)malloc(sizeof(Node));
        l->length=0;
        // printf("顺序表初始化成功");
        return l;
    }
    
    //随机产生一些数字
    int  produce_randomNum(orderList l)
    {
        srand(time(0));
        int n,m,a,i;
        printf("随机产生1-m范围的 n个数:\n");
        scanf("%d %d",&m,&n);//产生n个1-m之间的数字
        for(i=1; i<=n; i++)
        {
            a=rand()%m+1;
            //printf("%d ",a);
            l->R[++l->length].key=a;
    
        }
        return n;
    
    }
    
    //打印所有数字
    void print_orderList(orderList l)
    {
        int i;
        for(i=1; i<=l->length; i++)
            printf("%d ",l->R[i].key);
        printf("\n");
    }
    
    //逆序
    void reverse(orderList l)
    {
        int i;
        orderList l1=init_orderList();
        for(i=1; i<=l->length; i++)
            l1->R[i].key=l->R[i].key;
        for(i=1; i<=l->length; i++)
        {
            l->R[i].key=l1->R[l->length-i+1].key;
            //    printf("%d ",l1->R[i].key);
        }
        //printf("逆序输出:\n");
    
        //print_orderList(l);
    }
    
    //插入排序ElemType
    void insertSort(orderList l)
    {
        int i,j;
        int signal;
        compareTimes=moveTimes=0;
        for(i=2; i<=l->length; i++) //从第二个数开始依次与前面的数字比较
        {
            signal=l->R[i].key;//当前结点作为标志结点
            j=i-1;
            while(j>=1)//从当前结点下一个开始与标志结点比较
            {
                compareTimes++;
    
                if(l->R[j].key>signal)//大于标志结点,结点后移
                {
    
                    moveTimes++;
    
                    l->R[j+1]=l->R[j];
    
                    j--;
                }
                if(l->R[j].key<=signal)//小于标志结点,结束
                    break;
            }
            moveTimes++;
    
            l->R[j+1].key=signal;//第j+1个结点标志结点
        }
        printf("插入排序结果:\n");
        print_orderList(l);
        printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);
    
    }
    //希尔排序
    void shellSort(orderList l)
    {
        compareTimes=moveTimes=0;
        int gap,i,j;
        ElemType temp;
        for(gap=l->length/2; gap>0; gap/=2)
        {
            for(i=gap; i<=l->length; i++) //从每组最后开始进行插入排序
            {
                j=i;
                temp=l->R[j].key;//标志为当前组的最后一个
                while(j-gap>=1&&l->R[j-gap].key>temp)//j-gap为本组前一个数,本组还有数字并且本组当前数字大于标志数
                {
                    compareTimes++;
                    l->R[j]=l->R[j-gap];
                    moveTimes++;
                    j=j-gap;
                }
                compareTimes++;
                //本组当前数字小于标志数字
                l->R[j].key=temp;
                moveTimes++;
    
    
            }
    
        }
        printf("希尔排序结果:\n");
        print_orderList(l);
    
        printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);
    
    }
    
    
    //冒泡排序
    void buddleSort(orderList l)
    {
        compareTimes=moveTimes=0;
    
    
        int i,j,flag;
        KeyType temp;
        for(i=1; i<=l->length-1; i++)
        {
    
            flag=0;
            for(j=1; j<=l->length-i; j++)
            {
                compareTimes++;
                if(l->R[j+1].key<l->R[j].key)从最后一个数开始，比较相邻两个数的位置，如果第二个数小，就交换位置,这样一次循环后最小的就会被交换到最前面
                {
                    moveTimes++;
    
                    temp=l->R[j];
                    l->R[j]=l->R[j+1];
                    l->R[j+1]=temp;
                    flag=1;
                }
    
            }
            if(flag==0)
                break;//没有发生交换,则提前终止
        }
        printf("冒泡排序结果:\n");
        print_orderList(l);
        printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);
    
    }
    
    //快速排序
    void quickSort(orderList l,int left,int right)
    {
    
    
        if(left>=right)//当左区间>=区间时，一部分的排序完成
        {
            return;
        }
    
        int i=left,j=right;
        int pivotKey=l->R[left].key;//把第一个数作为一个枢纽
    
        while(i<j)
        {
            while(i<j&&l->R[j].key>=pivotKey)//从最后一个数开始依次与枢纽比较
            {
                  compareTimes++;
                j--;
            }
            compareTimes++;
            l->R[i].key=l->R[j].key;//把比枢纽小的元素交换到低端
            moveTimes++;
            while(i<j&&l->R[i].key<=pivotKey)
            {
                   compareTimes++;
    
                i++;
            }
             compareTimes++;
            l->R[j].key=l->R[i].key;//把比枢纽大的交换到高端
            moveTimes++;
    
    
        }
    
        l->R[i].key=pivotKey;// 当前元素变成枢纽元素
        moveTimes++;
    
        quickSort(l,left,i-1);//枢纽左面的数形成左区间，里面的数都比枢纽小
        quickSort(l,i+1,right);//枢纽右面的数字形成右区间，里面的书都比枢纽大
        //对左右两部分分别进行快速排序
    
    }
    void selectSort(orderList l)
    {
        int i,j,min,temp;
        compareTimes=moveTimes=0;
        for(i=1; i<=l->length-1; i++)
        {
            min=i;
            for(j=i+1; j<=l->length; j++)
            {
                if(l->R[j].key<l->R[min].key)
                {
                    min=j;
                    compareTimes++;
                    moveTimes++;
                }
                compareTimes++;
    
            }
            if(min!=i)
            {
                temp=l->R[i].key;
                l->R[i].key=l->R[min].key;
                l->R[min].key=temp;
                moveTimes++;
            }
            compareTimes++;
    
        }
       printf("简单选择排序结果:\n");
        print_orderList(l);
        printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);
    
    }
    void heapAdjust(orderList l,int par,int length)
    {
    
        int temp=l->R[par].key; //保存当前父节点
        int child=2*par;
    
        while(child<=length)
        {
            if(child+1<length&&l->R[child+1].key>l->R[child].key)//有右结点并且右结点小于左结点
                child++;
            compareTimes++;
    
            if(temp>=l->R[child].key)//父节点如果已经大于孩子结点,提前结束
                break;
            compareTimes++;
    
            l->R[par].key=l->R[child].key;//否则，把孩子结点的值赋给父结点
            moveTimes++;
    
            //选取孩子结点左结点，继续向下筛选
            par=child;
            child=2*par;
        }
    
        l->R[par].key=temp;
        //恢复原来的父结点
    }
    void heapSort(orderList l)
    {
        int i,j,temp;
        compareTimes=moveTimes=0;
    
        for(i=l->length/2; i>=1; i--)
            heapAdjust(l,i,l->length);
        for(i=l->length; i>=1; i--)
        {
            temp=l->R[i].key;
            l->R[i].key=l->R[1].key;
            l->R[1].key=temp;
            moveTimes++;
    
            heapAdjust(l,1,i);
    
        }
        printf("堆排序结果:\n");
        print_orderList(l);
        printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);
    
    }
    
    
    int main()
    {
        /* orderList l=init_orderList();
    
         int n=produce_randomNum(l);*/
        int choice;
        orderList l;
        int n;
        while(1)
        {
            printf("\t\t\t\t**************排序****************\n");
            printf("\t\t\t\t*                                *\n");
            printf("\t\t\t\t*         1.初始化数据           *\n");
            printf("\t\t\t\t*         2.直接插入排序         *\n");
            printf("\t\t\t\t*         3.希尔排序             *\n");
            printf("\t\t\t\t*         4.冒泡排序             *\n");
            printf("\t\t\t\t*         5.快速排序             *\n");
    
            printf("\t\t\t\t*         6.简单选择排序         *\n");
            printf("\t\t\t\t*         7.堆排序               *\n");
            printf("\t\t\t\t*         8.打印数据             *\n");
            printf("\t\t\t\t*         9.逆序输出             *\n");
            printf("\t\t\t\t*                                *\n");
            printf("\t\t\t\t*         0.退出                 *\n");
            printf("\t\t\t\t**********************************\n");
            printf("请选择(0-6):\n");
            scanf("%d",&choice);
            switch(choice)
            {
            case 1:
                l=init_orderList();
                n=produce_randomNum(l);
                break;
            case 2:
                insertSort(l);//直接插入排序
                getch();
                printf("正序:\n");
                reverse(l);
                insertSort(l);
                getch();
    
                 printf("逆序:\n");
                 reverse(l);
                insertSort(l);
                break;
    
            case 3:
                shellSort(l);//希尔排序
                getch();
                printf("正序:\n");
    
               shellSort(l);//希尔排序
                getch();
    
                 printf("逆序:\n");
                 reverse(l);
                shellSort(l);//希尔排序
    
                break;
            case 4:
                buddleSort(l);//冒泡排序
    
                break;
    
            case 5://快速排序
                compareTimes=moveTimes=0;
                quickSort(l,1,n);
                printf("快速排序结果:\n");
                print_orderList(l);
                printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);
                compareTimes=moveTimes=0;
                 getch();
                printf("正序:\n");
                quickSort(l,1,n);
                printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);
                compareTimes=moveTimes=0;
                getch();
    
                 printf("逆序:\n");
                 reverse(l);
                quickSort(l,1,n);
                printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);
    
                break;
            case 6:
                //选择排序
                selectSort(l);
    
                break;
            case 7:
                //堆排序
                heapSort(l);
                getch();
                printf("正序:\n");
    
                heapSort(l);
                getch();
    
                 printf("逆序:\n");
                 reverse(l);
                 heapSort(l);
                break;
            case 8:
                //打印数字
                print_orderList(l);
                break;
            case 9:
                //逆序输出数字
                reverse(l);
                break;
            case 0:
                //退出
                exit(0);
            default:
                printf("您输入的数据有误,请重新输入\n");
                break;
    
            }
            printf("请按任意键继续\n");
            getch();
            system("cls");
            continue;
        }
        return 0;
    }