网站 › 『编程语言区』 › 【C】6种排序算法效率比较

LSA 发表于 2017-4-7 19:41

【C】6种排序算法效率比较

刚学C时写的程序，实现了冒泡，选择，插入，希尔，快速和归并排序，并对此6种排序算法进行了简单的效率比较。算法这东西，该有用的时候就有用了.......(排序算法还是挺常用的)，有需要的可以参考一下,有注释。
(注：此程序要把6种算法都按一遍最后的6种比较才有效，暂时不想优化这个地方.......)

照例先放效果图：（色彩不好看，我当时是玩玩调颜色而已，有兴趣的可以自己换颜色）


代码打包：


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

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

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=rand()%101;
      str2=rand()%101;
      str3=rand()%101;
      str4=rand()%101;
      str5=rand()%101;
    }
    for(j=0;j<100;j++)
    {
      str1_1 = str1;
      str1_2 = str1;
      str1_3 = str1;
      str1_4 = str1;
      str1_5 = str1;
      str1_6 = str1;
    }
    for(j=0;j<100;j++)
    {
      str2_1 = str2;
      str2_2 = str2;
      str2_3 = str2;
      str2_4 = str2;
      str2_5 = str2;
      str2_6 = str2;
    }
    for(j=0;j<100;j++)
    {
      str3_1 = str3;
      str3_2 = str3;
      str3_3 = str3;
      str3_4 = str3;
      str3_5 = str3;
      str3_6 = str3;
    }
    for(j=0;j<100;j++)
    {
      str4_1 = str4;
      str4_2 = str4;
      str4_3 = str4;
      str4_4 = str4;
      str4_5 = str4;
      str4_6 = str4;
    }
    for(j=0;j<100;j++)
    {
      str5_1 = str5;
      str5_2 = str5;
      str5_3 = str5;
      str5_4 = str5;
      str5_5 = str5;
      str5_6 = str5;
    }
}

void printrand()   //打印生成的随机数组
{
    int i;
    printf("第一组\n");
    for(i=0;i<100;i++)
    {
      printf("%d ",str1);
    }
    printf("\n------------------------------------\n");
    printf("第二组\n");
    for(i=0;i<100;i++)
    {
      printf("%d ",str2);
    }
    printf("\n------------------------------------\n");
    printf("第三组\n");
    for(i=0;i<100;i++)
    {
      printf("%d ",str3);
    }
    printf("\n------------------------------------\n");
    printf("第四组\n");
    for(i=0;i<100;i++)
    {
      printf("%d ",str4);
    }
    printf("\n------------------------------------\n");
    printf("第五组\n");
    for(i=0;i<100;i++)
    {
      printf("%d ",str5);
    }
    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>str)
            {
                temp = str;
                str = str;
                str = 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;   //先设成最小的
      int temp;
      int index = i;   //记录下标
      for(j=i+1;j<n;j++)   //从i+1开始找最小值
      {
            compare++;
            if(str<Min)
            {
                Min = str;
                index = j;   //记录最小值的下标
            }
      }
      if(i!=index)   //不等于就交换
      {
      temp = str;   //以下3行为交换位置
      str = Min;
      str = 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;   //先把要插入的数存在tnum
      for(j=i-1;j>=0&&tnum<str;j--)   //从后往前比
      {
            compare++;
            str = str;   //移动元素
            mov++;
      }
      str = 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<str)
                {
                  temp = str;   //小的值放到temp
                  k = j - group;   //记录前面那个大的值的下标
                  while(k>=0&&str>temp)   //从后往前找
                  {
                        str = str;//移动元素
                        k = k - group;
                        mov++;
                  }
                  str = 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;
      if(l>=r) return;
      while(i!=j)
          {
            while(i<j&&str>=x)//右到左找第一个小于x的数
                {
                  qcompare++;
                  j--;
                }
            if(i<j)
            {
                str = str;
                qmov++;
            }
            while(i<j&&str<=x)   //左到右找第一个大于x的数
                {
                  qcompare++;
                  i++;
                }
            if(i<j)
            {
                str = str;
                qmov++;
            }
      }
      str = 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<=str)
      {
            gcompare++;
            str2 = str;
            gmov++;
      }
      else
      {
            gcompare++;
            str2 = str;
            gmov++;
      }
    }
    while(i<=m)   //i(左边)有剩
    {
      str2 = str;
      gmov++;
    }
    while(j<=n)   //j(右边)有剩
    {
      str2 = str;
      gmov++;
    }
    for(i=0;i<k;i++)   //合并好的整个序列复制到原序列中
    {
      str = str2;
      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;
    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;
}

LSA 发表于 2017-4-7 20:58

轻描淡写9714 发表于 2017-4-7 20:36
代码怎么弄得这种样式？

你是说吾爱代码的排版？这个直接贴代码就ok啦，吾爱利用了syntaxhighlighter可以代码高亮。
如果你是说我怎么写的话，我是用codeblocks写的，这个IDE可以自动缩进和高亮。

轻描淡写9714 发表于 2017-4-7 21:53

LSA 发表于 2017-4-7 20:58
你是说吾爱代码的排版？这个直接贴代码就ok啦，吾爱利用了syntaxhighlighter可以代码高亮。
如果你是说 ...

哦哦哦，知道了，谢谢！

轻描淡写9714 发表于 2017-4-7 20:23

新学程序的程序新生路过

轻描淡写9714 发表于 2017-4-7 20:24

楼主，求排版教程。代码好酷

LSA 发表于 2017-4-7 20:31

轻描淡写9714 发表于 2017-4-7 20:24
楼主，求排版教程。代码好酷

啥排版？

YY妖爱YY妖 发表于 2017-4-7 20:34

轻描淡写9714 发表于 2017-4-7 20:36

LSA 发表于 2017-4-7 20:31
啥排版？

代码怎么弄得这种样式？

jht168888 发表于 2017-4-7 20:59

高手,菜鸟来学习看看

logh 发表于 2017-4-7 21:05

我之前也写过一个 对比常用三个排序算法的速度快慢，没有你写得好！！！加油

锋范fast 发表于 2017-4-7 21:44

下载看看。。。

查看完整版本: 【C】6种排序算法效率比较