首页 » Program » C/C++ » 正文

6种排序算法效率比较

刚学C时写的程序,实现了冒泡,选择,插入,希尔,快速和归并排序,并对此6种排序算法进行了简单的效率比较。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <windows.h>

int str1[105],str2[105],str3[105],str4[105],str5[105];
int str1_1[105],str1_2[105],str1_3[105],str1_4[105],str1_5[105],str1_6[105];
int str2_1[105],str2_2[105],str2_3[105],str2_4[105],str2_5[105],str2_6[105];
int str3_1[105],str3_2[105],str3_3[105],str3_4[105],str3_5[105],str3_6[105];
int str4_1[105],str4_2[105],str4_3[105],str4_4[105],str4_5[105],str4_6[105];
int str5_1[105],str5_2[105],str5_3[105],str5_4[105],str5_5[105],str5_6[105];

int k,k1,k2,k3,k4,k5;
int qcompare,qmov;
int gcompare,gmov;
int avbubblingc,avselectc,avinsertionc,avshellc,avquickc,avmergec;
int avbubblingm,avselectm,avinsertionm,avshellm,avquickm,avmergem;

void randint()   //产生随机数数组
{
    int i,j;
    srand((unsigned)time(NULL));
    for(i=0;i<100;i++)   //模型数组
    {
        str1[i]=rand()%101;
        str2[i]=rand()%101;
        str3[i]=rand()%101;
        str4[i]=rand()%101;
        str5[i]=rand()%101;
    }
    for(j=0;j<100;j++)
    {
        str1_1[j] = str1[j];
        str1_2[j] = str1[j];
        str1_3[j] = str1[j];
        str1_4[j] = str1[j];
        str1_5[j] = str1[j];
        str1_6[j] = str1[j];
    }
    for(j=0;j<100;j++)
    {
        str2_1[j] = str2[j];
        str2_2[j] = str2[j];
        str2_3[j] = str2[j];
        str2_4[j] = str2[j];
        str2_5[j] = str2[j];
        str2_6[j] = str2[j];
    }
    for(j=0;j<100;j++)
    {
        str3_1[j] = str3[j];
        str3_2[j] = str3[j];
        str3_3[j] = str3[j];
        str3_4[j] = str3[j];
        str3_5[j] = str3[j];
        str3_6[j] = str3[j];
    }
    for(j=0;j<100;j++)
    {
        str4_1[j] = str4[j];
        str4_2[j] = str4[j];
        str4_3[j] = str4[j];
        str4_4[j] = str4[j];
        str4_5[j] = str4[j];
        str4_6[j] = str4[j];
    }
    for(j=0;j<100;j++)
    {
        str5_1[j] = str5[j];
        str5_2[j] = str5[j];
        str5_3[j] = str5[j];
        str5_4[j] = str5[j];
        str5_5[j] = str5[j];
        str5_6[j] = str5[j];
    }
}

void printrand()   //打印生成的随机数组
{
    int i;
    printf("第一组\n");
    for(i=0;i<100;i++)
    {
        printf("%d ",str1[i]);
    }
    printf("\n------------------------------------\n");
    printf("第二组\n");
    for(i=0;i<100;i++)
    {
        printf("%d ",str2[i]);
    }
    printf("\n------------------------------------\n");
    printf("第三组\n");
    for(i=0;i<100;i++)
    {
        printf("%d ",str3[i]);
    }
    printf("\n------------------------------------\n");
    printf("第四组\n");
    for(i=0;i<100;i++)
    {
        printf("%d ",str4[i]);
    }
    printf("\n------------------------------------\n");
    printf("第五组\n");
    for(i=0;i<100;i++)
    {
        printf("%d ",str5[i]);
    }
    printf("\n------------------------------------\n");
}

void bubbling_sort(int str[],int n)   //冒泡排序
{
    int i,j,temp,compare = 0,mov = 0;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            compare++;
            if(str[i]>str[j])
            {
                temp = str[i];
                str[i] = str[j];
                str[j] = temp;
                mov = mov + 3;
            }
        }
    }
    printf("第%d组数据:   比较次数->%d      移动次数%d\n",k++,compare,mov);
    avbubblingc = avbubblingc + compare;
    avbubblingm = avbubblingm + mov;
}

void select_sort(int str[],int n)   //选择排序
{
    int i,j,compare = 0,mov = 0;
    for(i=0;i<n;i++)   //进行n-1轮遍历
    {
        int Min = str[i];   //先设成最小的
        int temp;
        int index = i;   //记录下标
        for(j=i+1;j<n;j++)   //从i+1开始找最小值
        {
            compare++;
            if(str[j]<Min)
            {
                Min = str[j];
                index = j;   //记录最小值的下标
            }
        }
        if(i!=index)   //不等于就交换
        {
        temp = str[i];   //以下3行为交换位置
        str[i] = Min;
        str[index] = temp;
        mov = mov + 3;
        }
    }
    printf("第%d组数据       比较次数->%d        移动次数->%d\n",k1++,compare,mov);
    avselectc = avselectc + compare;
    avselectm = avselectm + mov;
}

void insertion_sort(int str[],int n)   //插入排序
{
    int i,j,tnum;
    int compare = 0,mov = 0;
    for(i=1;i<n;i++)   //遍历n-1次就ok
    {
        tnum = str[i];   //先把要插入的数存在tnum
        for(j=i-1;j>=0&&tnum<str[j];j--)   //从后往前比
        {
            compare++;
            str[j+1] = str[j];   //移动元素
            mov++;
        }
        str[j+1] = tnum;   //找到插入位置了
    }
    printf("第%d组数据       比较次数->%d        移动次数->%d\n",k2++,compare,mov);
    avinsertionc = avinsertionc + compare;
    avinsertionm = avinsertionm + mov;
}

void shell_sort(int str[],int n)
{
    int group,i,j,k,temp;
    int compare = 0,mov = 0;
    for(group=n/2;group>0;group=group/2)   //分组
    {
        for(i=0;i<group;i++)   //有i组
        {
            for(j=i+group;j<n;j=j+group)   //对这些组的元素进行插入排序
            {
                compare++;
                if(str[j]<str[j-group])
                {
                    temp = str[j];   //小的值放到temp
                    k = j - group;   //记录前面那个大的值的下标
                    while(k>=0&&str[k]>temp)   //从后往前找
                    {
                        str[k+group] = str[k];  //移动元素
                        k = k - group;
                        mov++;
                    }
                    str[k+group] = temp;   //找到插入位置了
                }
            }
        }
    }
    printf("第%d组数据       比较次数->%d        移动次数->%d\n",k3++,compare,mov);
    avshellc = avshellc + compare;
    avshellm = avshellm + mov;
}

void quick_sort(int str[],int l,int r)   //分治快排
{
        int i = l,j = r,x = str[l];
        if(l>=r) return;
        while(i!=j)
          {
            while(i<j&&str[j]>=x)  //右到左找第一个小于x的数
                {
                    qcompare++;
                    j--;
                }
            if(i<j)
            {
                str[i] = str[j];
                qmov++;
            }
            while(i<j&&str[i]<=x)   //左到右找第一个大于x的数
                {
                    qcompare++;
                    i++;
                }
            if(i<j)
            {
                str[j] = str[i];
                qmov++;
            }
        }
        str[i] = x;   //左右指针重合了就是x
        quick_sort(str,l,i-1);   //递归左边
        quick_sort(str,i+1,r);   //递归右边
}

void merge_array(int str[],int first,int mid,int last,int str2[])  //合并两个有序序列-----并
{
    int i = first,m = mid,n = last;
    int j = mid + 1;
    int k = 0;
    while(i<=m&&j<=n)  //比较看谁小就入谁
    {

        if(str[i]<=str[j])
        {
            gcompare++;
            str2[k++] = str[i++];
            gmov++;
        }
        else
        {
            gcompare++;
            str2[k++] = str[j++];
            gmov++;
        }
    }
    while(i<=m)   //i(左边)有剩
    {
        str2[k++] = str[i++];
        gmov++;
    }
    while(j<=n)   //j(右边)有剩
    {
        str2[k++] = str[j++];
        gmov++;
    }
    for(i=0;i<k;i++)   //合并好的整个序列复制到原序列中
    {
        str[first+i] = str2[i];
        gmov++;
    }
}

void merge_sort(int str[],int first,int last,int str2[])
{
    if(first<last)
    {
        int mid = (first+last) / 2;   //-----归
        merge_sort(str,first,mid,str2);   //左边有序
        merge_sort(str,mid+1,last,str2);   //右边有序
        merge_array(str,first,mid,last,str2);   //将两个有序序列合并
    }
}

void windows()   //菜单
{
    printf("!------------------------欢迎使用LSA内部排序测试系统--------------------------!\n\n\n");
    printf("1-显示生成的5组随机数组                                 查看冒泡排序的效率对比-2\n");
    printf("3-查看选择排序的效率对比                                查看插入排序的效率对比-4\n");
    printf("5-查看希尔排序的效率对比                                查看快速排序的效率对比-6\n");
    printf("7-查看归并排序的效率对比                                     查看6种的效率对比-8\n");
    printf("9-版权声明                                                           退出系统-10\n");
}

char retu()   //返回选择
{
    char choose1;
    printf("r-返回菜单                                                           e-退出系统\n");
    scanf("%c",&choose1);
    return choose1;
}

void exitsort()   //退出系统
{
    printf("感谢您对LSA内部排序测试系统的支持,欢迎再次光临!\n");
    exit(0);
}


void choo()
{
    int choose;
    int str2[105];
    s1:windows();
    while(1)
    {
    scanf("%d",&choose);
    getchar();
    switch(choose)
    {
        case 1:system("CLS");
                printrand();
                if(retu()=='r')
                {
                    system("CLS");
                    goto s1;
                }
                else
                {
                    system("CLS");
                    exitsort();
                }
                break;
        case 2:system("CLS");
                printf("冒泡排序对5组数据的效率对比\n\n");
                bubbling_sort(str1_1,100);
                bubbling_sort(str2_1,100);
                bubbling_sort(str3_1,100);
                bubbling_sort(str4_1,100);
                bubbling_sort(str5_1,100);
                if(retu()=='r')
                {
                    system("CLS");
                    goto s1;
                }
                else
                {
                    system("CLS");
                    exitsort();
                }
                break;
        case 3:system("CLS");
                printf("选择排序对5组数据的效率对比\n");
                select_sort(str1_2,100);
                select_sort(str2_2,100);
                select_sort(str3_2,100);
                select_sort(str4_2,100);
                select_sort(str5_2,100);
                if(retu()=='r')
                {
                    system("CLS");
                    goto s1;
                }
                else
                {
                    system("CLS");
                    exitsort();
                }
                break;
        case 4:system("CLS");
                printf("插入排序对5组数据的效率对比\n");
                insertion_sort(str1_3,100);
                insertion_sort(str2_3,100);
                insertion_sort(str3_3,100);
                insertion_sort(str4_3,100);
                insertion_sort(str5_3,100);
                if(retu()=='r')
                {
                    system("CLS");
                    goto s1;
                }
                else
                {
                    system("CLS");
                    exitsort();
                }
                break;
        case 5:system("CLS");
                printf("希尔排序对5组数据的效率对比\n");
                shell_sort(str1_4,100);
                shell_sort(str2_4,100);
                shell_sort(str3_4,100);
                shell_sort(str4_4,100);
                shell_sort(str5_4,100);
                if(retu()=='r')
                {
                    system("CLS");
                    goto s1;
                }
                else
                {
                    system("CLS");
                    exitsort();
                }
                break;
        case 6:system("CLS");
                printf("快速排序对5组数据的效率对比\n");
                quick_sort(str1_5,0,99); printf("第%d组数据       比较次数->%d        移动次数->%d\n",k4++,qcompare,qmov); avquickc = avquickc + qcompare; avquickm = avquickm + qmov; qcompare = 0,qmov = 0;
                quick_sort(str2_5,0,99); printf("第%d组数据       比较次数->%d        移动次数->%d\n",k4++,qcompare,qmov); avquickc = avquickc + qcompare; avquickm = avquickm + qmov; qcompare = 0,qmov = 0;
                quick_sort(str3_5,0,99); printf("第%d组数据       比较次数->%d        移动次数->%d\n",k4++,qcompare,qmov); avquickc = avquickc + qcompare; avquickm = avquickm + qmov; qcompare = 0,qmov = 0;
                quick_sort(str4_5,0,99); printf("第%d组数据       比较次数->%d        移动次数->%d\n",k4++,qcompare,qmov); avquickc = avquickc + qcompare; avquickm = avquickm + qmov; qcompare = 0,qmov = 0;
                quick_sort(str5_5,0,99); printf("第%d组数据       比较次数->%d        移动次数->%d\n",k4++,qcompare,qmov); avquickc = avquickc + qcompare; avquickm = avquickm + qmov; qcompare = 0,qmov = 0;
                if(retu()=='r')
                {
                    system("CLS");
                    goto s1;
                }
                else
                {
                    system("CLS");
                    exitsort();
                }
                break;
        case 7:system("CLS");
                printf("归并排序对5组数据的效率对比\n");
                merge_sort(str1_6,0,99,str2); printf("第%d组数据       比较次数->%d        移动次数->%d\n",k5++,gcompare,gmov); avmergec = avmergec + gcompare; avmergem = avmergem + gmov; gcompare = 0,gmov = 0;
                merge_sort(str2_6,0,99,str2); printf("第%d组数据       比较次数->%d        移动次数->%d\n",k5++,gcompare,gmov); avmergec = avmergec + gcompare; avmergem = avmergem + gmov; gcompare = 0,gmov = 0;
                merge_sort(str3_6,0,99,str2); printf("第%d组数据       比较次数->%d        移动次数->%d\n",k5++,gcompare,gmov); avmergec = avmergec + gcompare; avmergem = avmergem + gmov; gcompare = 0,gmov = 0;
                merge_sort(str4_6,0,99,str2); printf("第%d组数据       比较次数->%d        移动次数->%d\n",k5++,gcompare,gmov); avmergec = avmergec + gcompare; avmergem = avmergem + gmov; gcompare = 0,gmov = 0;
                merge_sort(str5_6,0,99,str2); printf("第%d组数据       比较次数->%d        移动次数->%d\n",k5++,gcompare,gmov); avmergec = avmergec + gcompare; avmergem = avmergem + gmov; gcompare = 0,gmov = 0;
                if(retu()=='r')
                {
                    system("CLS");
                    goto s1;
                }
                else
                {
                    system("CLS");
                    exitsort();
                }
                break;
        case 8:system("CLS");
                printf("6种排序对5组数据的效率对比\n");
                printf("冒泡排序:      平均比较次数%d         平均移动次数%d\n",avbubblingc/5,avbubblingm/5);
                printf("选择排序:      平均比较次数%d         平均移动次数%d\n",avselectc/5,avselectm/5);
                printf("插入排序:      平均比较次数%d         平均移动次数%d\n",avinsertionc/5,avinsertionm/5);
                printf("希尔排序:      平均比较次数%d         平均移动次数%d\n",avshellc/5,avshellm/5);
                printf("快速排序:      平均比较次数%d         平均移动次数%d\n",avquickc/5,avquickm/5);
                printf("归并排序:      平均比较次数%d         平均移动次数%d\n",avmergec/5,avmergem/5);
                if(retu()=='r')
                {
                    system("CLS");
                    goto s1;
                }
                else
                {
                    system("CLS");
                    exitsort();
                }
                break;
        case 9:system("CLS");
                printf("这里是极为重要的版权声明:\n");
                printf("LSA内部排序系统允许引用或修改或转载,须注明出处是LSA内部排序系统!\n                            请尊重原创!\n                             多谢合作!\n");
                if(retu()=='r')
                {
                    system("CLS");
                    goto s1;
                }
                else
                {
                    system("CLS");
                    exitsort();
                }
                break;
        case 10:system("CLS");
                exitsort();
                break;
    }
    }
}

int main()
{
    system("color 12");
    randint();
    choo();
    return 0;
}


赞 (0)

Comment