鱼C论坛

 找回密码
 立即注册
查看: 2351|回复: 5

排序算法的比较

[复制链接]
发表于 2019-12-23 22:24:46 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
利用随机函数产生 30000 个随机整数, 利用插入排序、 起泡排序、 选择排序、 快速排序、 堆排序、 归并排序等排序方法进行排序, 并统计每一种排序上机所花费的时间和次数。
  1. Status PrintfSqlist(int N,Sqlist L)                               
  2. {
  3.         int i;
  4.        
  5.         printf("数据个数:");//输出数据个数
  6.         printf("%d\n",L.length);
  7.        
  8.         printf("排序后的数据:(从左向右依次增大)\n");//输出数据
  9.         for(i=1;i<=N;i++)
  10.                 printf("%7.2d   ",L.r[i]);
  11.         printf("\n");
  12.    


  13.         return OK;
  14. }

  15. //***************************************************************
  16. //                    直接插入排序
  17. //***************************************************************
  18. Status InsertSort(Sqlist &L)                        //参考书P265算法10.1               
  19. {
  20.         int i,j;

  21.         if(L.length==0)
  22.         {
  23.                 printf("要排序的数据为空!");
  24.                 return ERROR;
  25.         }

  26.         for(i=2;i<=L.length;i++)
  27.         {
  28.                 if(L.r[i]<L.r[i-1])  //将L.r[i]插入有序子表       
  29.                 {
  30.                         L.r[0]=L.r[i];  //复制为监视哨
  31.                         L.r[i]=L.r[i-1];                                            
  32.                         for(j=i-2;L.r[0]<L.r[j];j--)
  33.                         {
  34.                                 L.r[j+1]=L.r[j];  //记录后移
  35.                         }
  36.                        
  37.                         L.r[j+1]=L.r[0];  //插入到正确位置
  38.                 }
  39.         }
  40.         return OK;
  41. }

  42. //***************************************************************
  43. //                      折半插入排序
  44. //***************************************************************
  45. Status BInsertSort(Sqlist &L)                             //参考书P267算法10.2       
  46. {
  47.         int i,j,mid,low,high;

  48.         if(L.length==0)
  49.         {
  50.                 printf("要排序的数据为空!");
  51.                 return ERROR;
  52.         }
  53.        
  54.         for(i=2;i<=L.length;i++)
  55.         {
  56.                 L.r[0]=L.r[i];  //将L.r[i]暂存在L.r[0]
  57.                 low=1;
  58.                 high=i-1;
  59.                
  60.                 while(low<=high)  //在r[low..high]中折半查找有序插入的位置
  61.                 {
  62.                         mid=(low+high)/2;
  63.                        
  64.                         if(L.r[0]<L.r[mid])  //插入点在低半区                     
  65.                         {
  66.                                 high=mid-1;
  67.                         }
  68.                         else
  69.                         {
  70.                                 low=mid+1;  //插入点在高半区
  71.                         }
  72.                 }//while
  73.                 for(j=i-1;j>=high+1;j--)  //插入点后的数据后移                               
  74.                 {
  75.                         L.r[j+1]=L.r[j];                                                                                         
  76.                 }
  77.                 L.r[high+1]=L.r[0];          //将数据插入
  78.         }//for
  79.         return OK;
  80. }

  81. /********************************************************************************
  82.                               希尔排序
  83. *********************************************************************************/
  84.                                                                   //参考书P272算法10.4及10.5
  85. /*Status ShellInsert(Sqlist &L,int dk)                        //希尔插入排序
  86. {                       
  87.         int i,j;                                                                                                                        //前后位置的增量是dk

  88.         for(i=dk+1;i<=L.length;i++)                                                                                        //r[0]只是暂存单元,不是哨兵,
  89.         {                               
  90.                 if(L.r[i]<L.r[i-dk])                                                                                        //将L.r[i]插入有序增量子表
  91.                 {
  92.                         L.r[0]=L.r[i];                                                                                                //暂存L.r[0]

  93.                         for(j=i-dk;j>0 && L.r[0]<L.r[j];j-=dk)
  94.                         {
  95.                                 L.r[j+dk]=L.r[j];                                                                                //记录后移,查找插入位置
  96.                         }
  97.                         L.r[j+dk]=L.r[0];                                                                                        //插入
  98.                 }
  99.         }
  100.         return OK;
  101. }

  102. Status ShellSort(Sqlist &L,int dlta[5],int t)      //希尔排序
  103. {               
  104.         int i;

  105.         if(L.length==0)
  106.         {
  107.                 printf("要排序的数据为空!");
  108.                 return ERROR;
  109.         }

  110.         for(i=0;i<t;i++)
  111.         {
  112.                 ShellInsert(L,dlta[i]);                                                        //一趟增量为dlta[k]的插入排序
  113.         }
  114.         return OK;
  115. }
  116. */

  117. //**************************************************************
  118. //                         起泡排序
  119. //**************************************************************
  120. Status BubbleSort(Sqlist &L)                               
  121. {
  122.         int i,j,t;

  123.         if(L.length==0)
  124.         {
  125.                 printf("要排序的数据为空!");
  126.                 return ERROR;
  127.         }

  128.        
  129.         for(i=1;i<=L.length-1;i++)                                                                                       
  130.         {
  131.                 for(j=1;j<=L.length-i;j++)
  132.                 {
  133.                         if(L.r[j]>L.r[j+1])         //前面的数据>后面数据时
  134.                         {               
  135.                                 t=L.r[j+1];                                                                                               
  136.                                 L.r[j+1]=L.r[j];
  137.                                 L.r[j]=t;  //将元素交换
  138.                         }
  139.                 }
  140.         }
  141.         return OK;
  142. }

  143. //****************************************************
  144. //                   快速排序
  145. //****************************************************

  146. int Partition(Sqlist &L, int low, int high) //交换顺序表中子表L.r[low..high]的记录,使得枢轴记录到位,并返回其所在位置,此时在它之前(后)的记录均不大于它
  147. {
  148.         int pivotkey;  //记录关键字
  149.         L.r[0]=L.r[low];  //用子表的第一个纪录作枢轴纪录
  150.         pivotkey=L.r[low];  //用枢轴纪录关键字                              
  151.         while (low<high)                                       
  152.         {
  153.                 while(low<high && L.r[high]>=pivotkey)
  154.                 {
  155.                         high--;
  156.                 }
  157.                 L.r[low]= L.r[high];  //将比枢轴记录小的记录移到低端
  158.                 while(low<high && L.r[low]<=pivotkey)
  159.                 {
  160.                         low++;
  161.                 }
  162.                 L.r[high]=L.r[low];  //将比枢轴记录大的数移到高端
  163.    }
  164.      L.r[low]=L.r[0];  //枢轴记录到位
  165.      return low;
  166. }//Partition函数

  167. void Qsort (Sqlist &L,int low, int high)
  168. {
  169.         int pivotloc;
  170.         if  (low<high)  //长度大于1,可以进行                     
  171.         {
  172.                 pivotloc=Partition(L, low ,high);
  173.                 Qsort(L,low,pivotloc-1);   //对低子表递归排序,pivotloc是枢轴位置
  174.                 Qsort(L,pivotloc+1,high);  //对高子表递归排序
  175.         }
  176. }//Qsort函数

  177. Status  QuickSort (Sqlist &L)
  178. {
  179.     if(L.length==0)
  180.         {
  181.                 printf("要排序的数据为空!");
  182.                 return ERROR;
  183.         }
  184.         Qsort(L,1,L.length);
  185.         return OK;
  186. }//QuickSort



  187. //**********************************************
  188. //                 选择排序
  189. //**********************************************
  190. Status ChooseSort(Sqlist &L)                                       
  191. {
  192.         int i,j,k,t;

  193.         if(L.length==0)
  194.         {
  195.                 printf("没有数据!");
  196.                 return ERROR;
  197.         }
  198.        
  199.         for(i=1;i<=L.length;i++)  //排序的趟数
  200.         {
  201.                 k=i;
  202.                 for(j=i+1;j<=L.length;j++)  //比较第i个元素以及其后的数据中最小的
  203.                 {
  204.                         if(L.r[j]<L.r[k])
  205.                                 k=j;
  206.                 }
  207.                
  208.                 if(i!=j)  //将最小数据赋值给L.r[i]
  209.                 {
  210.                         t=L.r[i];
  211.                         L.r[i]=L.r[k];
  212.                         L.r[k]=t;
  213.                 }
  214.         }
  215.         return OK;
  216. }

  217. //****************************************
  218. //                  堆排序
  219. //****************************************
  220. Status HeapAdjust(Sqlist &L,int s,int m)  //调整L.r[s]的关键字,使L.r[s~m]成大顶堆
  221. {
  222.         int i;                                                                                       
  223.         L.r[0]=L.r[s];

  224.         for(i=2*s;i+1<=m;i*=2)  //沿数据较大的孩子结点向下筛选
  225.         {
  226.                 if(i<m && L.r[i]<L.r[i+1])  //i为数据较大的记录下标
  227.                         i++;
  228.                
  229.                 if(L.r[0]>=L.r[i])  //L.r[0]插入在S位置上
  230.                         break;
  231.                
  232.                 L.r[s]=L.r[i];
  233.                 s=i;
  234.         }
  235.         L.r[s]=L.r[0];          //插入新数据        

  236.         return OK;
  237. }

  238. Status HeapSort(Sqlist &L)  //堆排序
  239. {
  240.         int i,t;

  241.         if(L.length==0)
  242.         {
  243.                 printf("没有数据!");
  244.                 return ERROR;
  245.         }

  246.         for(i=L.length/2;i>0;i--)
  247.                 HeapAdjust(L,i,L.length);
  248.        
  249.         for(i=L.length;i>1;i--)
  250.         {
  251.                 t=L.r[1];  //将堆顶记录和当前未经排序的子序列L.r[1..i]中最后一个记录互换
  252.                 L.r[1]=L.r[i];
  253.                 L.r[i]=t;
  254.                
  255.                 HeapAdjust(L,1,i-1);  //将L.r[1..i-1]重新调整为大顶堆
  256.         }
  257.         return OK;
  258. }



  259. //**************************************************
  260. //                    基数排序
  261. //**************************************************
  262. typedef struct node{
  263.         int  key;
  264.         node *next;
  265. }RecType;

  266. Status         RadixSort(Sqlist L)       
  267. {
  268.         int t,i,j,k,d,n=1,m;
  269.         RecType *p,*s,*q,*head[10],*tail[10];  //定义各链队的首尾指针
  270.        
  271.         for(i=1;i<=L.length;i++)  //将顺序表转化为链表
  272.         {
  273.                 s=(RecType*)malloc(sizeof(RecType));
  274.                 s->key=L.r[i];
  275.                 if(i==1)  //当为第一个元素时
  276.                 {
  277.                         q=s;
  278.                         p=s;
  279.                         t++;
  280.                 }
  281.                 else               
  282.                 {
  283.                         q->next=s;  //将链表连接起来
  284.                         q=s;
  285.                         t++;
  286.                 }
  287.                 q->next=NULL;
  288.         }
  289.        
  290.         d=1;                                                                                       
  291.        
  292.         while(n>0)   //将每个元素分配至各个链队
  293.         {
  294.                 for(j=0;j<10;j++)  //初始化各链队首、尾指针
  295.                 {
  296.                         head[j] = NULL;
  297.                         tail[j] = NULL;
  298.                 }
  299.                 while(p!=NULL)  //对于原链表中的每个结点循环
  300.                 {
  301.                         k=p->key/d;
  302.                         k=k%10;
  303.                         if(head[k]==NULL)  //进行分配
  304.                         {
  305.                                 head[k]=p;
  306.                                 tail[k]=p;
  307.                         }
  308.                         else
  309.                         {
  310.                                 tail[k]->next=p;
  311.                                 tail[k]=p;
  312.                         }
  313.                         p=p->next;  //取下一个待排序的元素
  314.                 }
  315.                
  316.                 p=NULL;  //用于收集第一个元素时的判断
  317.                
  318.                 for(j=0;j<10;j++)  //对每一个链队循环, 搜集每一个元素
  319.                 {
  320.                         if(head[j]!=NULL)  //进行搜集
  321.                         {
  322.                                 if(p==NULL)                                               
  323.                                 {
  324.                                         p=head[j];
  325.                                         q=tail[j];
  326.                                 }
  327.                                 else
  328.                                 {
  329.                                         q->next=head[j];
  330.                                         q=tail[j];
  331.                                 }
  332.                         }
  333.                 }
  334.                 q->next=NULL;  //最后一个结点的next置为空
  335.                 d=d*10;
  336.                
  337.                 n=0;
  338.                 m=1;
  339.                 while(m<=L.length)  //判断当L中的元素都除d后是不是都为零了
  340.                 {
  341.                         if((L.r[m]/d)!=0)
  342.                         {
  343.                                 n++;
  344.                                 m++;
  345.                         }
  346.                         else
  347.                                 m++;

  348.                 }
  349.         }
  350.        
  351.         i=1;
  352.         while(p!=NULL) //将链表转换为顺序表
  353.         {
  354.                 L.r[i]=p->key;
  355.                 i++;
  356.                 p=p->next;
  357.         }
  358.         return OK;
  359. }
复制代码

求助大佬  运行结果就是   算法名称     排序次数     运行时间  这种格式  请大佬帮帮忙
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2019-12-23 22:53:47 | 显示全部楼层

回帖奖励 +30 鱼币

怎么看起来这么像作业呢?
作业就好好做,认真听了课的话这个肯定不难
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-12-24 08:46:30 | 显示全部楼层
Croper 发表于 2019-12-23 22:53
怎么看起来这么像作业呢?
作业就好好做,认真听了课的话这个肯定不难

这是我的课程设计,换了几种方法都不能运行,所以才来问的
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-12-25 07:42:18 From FishC Mobile | 显示全部楼层
那么你为什么不把你不能运行的代码放上来,让大家帮你检查一下哪儿不对呢?
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-12-25 13:39:29 | 显示全部楼层
各位大神啊,排序方法那么多,是不是要求每种排序法都要精通啊?????
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-12-25 17:42:31 | 显示全部楼层
Croper 发表于 2019-12-25 07:42
那么你为什么不把你不能运行的代码放上来,让大家帮你检查一下哪儿不对呢?

我重新发了一个帖子,能不能麻烦你去看看啊,我那里把代码发上去了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-12 23:23

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表