排序算法比较程序

功能要求如下：

排序算法比较: shellsort, quicksort, heapsort, mergesort 的算法实现 ，

对同样数据集的排序时间比较。

源代码：

# include <stdio.h>
# include <time.h>
# define MAXSIZE 2000
typedef struct{
　　int key[MAXSIZE];
　　int length;
}list;
long int　compCount;
long int　shiftCount;
void menu(int *m)/*retun m*/
{
　　int i;
　　char menu[6][15]={"1 CREATE ","2 IMPORT ","3 SORT","4 SHOW RESULT",
　　　　　　　　　　　　　 "5 SAVE RESULT","6 EXIT"};
　　clrscr();
　　printf("SORT COMPARE SYSTEM\n");
　　for (i=0;i<6;i++) printf("%s\n",menu[i]);
　　printf("\n Please Select (1-6):\n");
　 
　　scanf("%d",m);
}
void menusort(int *m)/*retun m*/
{
　　int i;
　　char menusort[5][15]={"1 SHELL SORT","2 QUICK SORT","3 HEAP SORT",
　　　　　　　　　　　　　　"4 MERGE SORT","5 ALL SORT"};
　 
　　clrscr();
　　printf("SORT\n");
　　for(i=0;i<5;i++) printf("%s\n",menusort[i]);
　　printf("\n Please Select (1-5):\n");
　 
　　scanf("%d",m);
}
void menushow(int *m)/*retun m*/
{
　　int i;
　　char menushow[4][20]={"1 SHELL SORT RESULT","2 QUICK SORT RESULT",
　　　　　　　　　　　　　　"3 HEAP SORT RESULT","4 MERGE SORT RESULT"};
　 
　　clrscr();
　　printf("SHOW SORT RESULT\n");
　　for(i=0;i<4;i++) printf("%s\n",menushow[i]);
　　printf("\n Please Select (1-4):\n");
　 
　　scanf("%d",m);
}
void menusave(int *m)
{
　　int i;
　　char menusave[4][20]={"1 SHELL SORT RESULT","2 QUICK SORT RESULT",
　　　　　　　　　　　　　 "3 HEAP SORT RESULT","4 MERGE SORT RESULT"};
　 
　　clrscr();
　　printf("SAVE:\n");
　　for (i=0;i<4;i++) printf("%s\n",menusave[i]);
　　printf("\n Please Select (1-4):\n");
　 
　　scanf("%d",m);
}
void create(list *L)
{
　　int i;
　 
　　printf("HOW MANY DATA?\n");
　　scanf("%d",&((*L).length));
　 
　　for(i=1;i<=(*L).length;i++)
　　{
　　　　printf("\nPLEASE INPUT THE %dth DATA:\n",i);
　　　　scanf("%d",&(*L).key[i]);
　　}
　　printf("\nCREATE COMPLETE !\n");
　　　 
}
int listopen(list *L,char *filename)
{
　　int k=1;
　　FILE *data;
　 
　　data=NULL;
　　data=fopen(filename,"rb");
　 
　　while (! feof(data))
　　　　{
　　　　　　fscanf(data,"%d",&(*L).key[k]);
　　　　　　k++;
　　　　}
　　　　(*L).length=k-1;
}
void import(list *L)/*fix L*/
{
　　char filename[255];
　　int i;
　　printf("\nPLEASE INPUT THE FILE PATH AND NAME:\n");
　　scanf("%s",filename);
　　clrscr();
　　listopen(L,filename);
　　for(i=1;i<(*L).length;i++) printf("%d ",(*L).key[i]);
　　printf("\nPRESS ANYKEY RETURN TO MAINMENU...\n");
　　getch();
}
void save(list L)
{
　　FILE *data;
　　char filename[255];
　　int r;
　　printf("\nPLEASE INPUT THE FILE PATH AND NAME:\n");
　　scanf("%s",filename);
　　data=fopen(filename,"wb");
　　for(r=1;r<=L.length;r++) fprintf(data,"%d\n",L.key[r]);
　　fclose(data);
　　printf("SAVE OK! \n PRESS ANY KEY TO RETURN THE MAINMENU... ");
　　getch();
　　　 
}
list shellsort(list L)/*retun L_SHELL*/
{
　　int i,j,gap,x,n;
　 
　　compCount=shiftCount=0;
　　n=L.length;
　　gap=n/2;
　　while (gap>0)
　　{
　　　　compCount++;
　　　　for(i=gap+1;i<=n;i++)
　　　　{
　　　　　　compCount++;
　　　　　　j=i-gap;
　　　　　　while(j>0)
　　　　　　{
　　　　　　　　compCount++;
　　　　　　　　if(L.key[j]>L.key[j+gap])
　　　　　　　　{
　　　　　　　　　　compCount++;
　　　　　　　　　　x=L.key[j];shiftCount++;
　　　　　　　　　　L.key[j]=L.key[j+gap];shiftCount++;
　　　　　　　　　　L.key[j+gap]=x;shiftCount++;
　　　　　　　　　　j=j-gap;
　　　　　　　　}
　　　　　　　　else j=0;
　　　　　　}
　　　　　　　 
　　　　}
　　　　gap=gap/2;
　　}
　　return L;
}
void shell(list L,list *LS,float *timeshell)/*return LS,timeshell.
　　　　　　　　　　　　　　　　　　　　　　　 MUST add an "getch"!!*/
{
　　clock_t start,end;
　 
　　　 
　　start=clock();
　　(*LS)=shellsort(L);
　　end=clock();
　 
　　*timeshell=(end-start)/CLK_TCK;
　 
　　printf("\nSHELLSORT COST TIME :%f SECONDS.",*timeshell);
　　printf("Compare %d times.Shfit %d times.\n",compCount,shiftCount);
}
int Partition(list * pL,int low,int high)
{
　　int pivotkey;
　　pL->key[0]=pL->key[low];shiftCount++;
　　pivotkey=pL->key[low];shiftCount++;
　　while(low<high)
　　{
　　　　compCount++;
　　　　while(low<high && pivotkey<=(pL->key[high]))
　　　　　　 {compCount++;compCount++; --high;}
　　　　pL->key[low]=pL->key[high];shiftCount++;
　　　　while(low<high && (pL->key[low])<=pivotkey)
　　　　　　 {compCount++;compCount++; ++low;}
　　　　pL->key[high]=pL->key[low];shiftCount++;
　　}
　　pL->key[low]=pL->key[0];shiftCount++;
　　return low;
}/*Partition*/
void QSort(list * pL,int low,int high)
{
　　int pivotloc;
　　if(low<high)
　　{
　　　　compCount++;
　　　　pivotloc=Partition(pL,low,high);
　　　　QSort(pL,low,pivotloc-1);
　　QSort(pL,pivotloc+1,high);
　　}
}/*QSort*/
list QuickSort(list pL)
{
　　compCount=shiftCount=0;
　　QSort(&pL,1,pL.length);
　　return pL;
}/*QuickSort*/
void quick(list L,list *LQ,float *timequick)/*MUST add an "getch"!!*/
{
　　clock_t start,end;
　　start=clock();
　　(*LQ)=QuickSort(L);
　　end=clock();
　 
　　*timequick=(end-start)/CLK_TCK;
　 
　　printf("\nQUICKSORT COST TIME :%f SECONDS.",*timequick);
　　printf("Compare %d times.Shfit %d times.\n",compCount,shiftCount);
}
void sift(list L,int l,int m)
{
　　int i,j,x;
　　i=l;
　　j=2*i;
　　x=L.key[i];
　　while (j<=m)
　　{
　　　　compCount++;
　　　　if(j<m && L.key[j]<L.key[j+1]) {j++;compCount++;compCount++;}
　　　　if(x<L.key[j])
　　　　{
　　　　　　compCount++;
　　　　　　L.key[i]=L.key[j];shiftCount++;
　　　　　　i=j;shiftCount++;
　　　　　　j=2*i;
　　　　}
　　　　else j=m+1;
　　}
　　L.key[i]=x;shiftCount++;
}
list heapsort(list L)
{
　　int i,w;
　 
　　compCount=shiftCount=0;
　　for (i=L.length/2;i>=1;i--) {sift(L,i,L.length);compCount++;}
　　for (i=L.length;i>=2;i--)
　　{
　　　　compCount++;
　　　　w=L.key[i];shiftCount++;
　　　　L.key[i]=L.key[1];shiftCount++;
　　　　L.key[1]=w;shiftCount++;
　　　　sift(L,i-1,1);
　　}
　　return L;
}
void heap(list L,list *LH,float *timeheap)
{
　　clock_t start,end;
　 
　　　 
　　start=clock();
　　(*LH)=heapsort(L);
　　end=clock();
　 
　　*timeheap=(end-start)/CLK_TCK;
　 
　　printf("\nHEAPSORT COST TIME :%f SECONDS.",*timeheap);
　　printf("Compare %d times.Shfit %d times.\n",compCount,shiftCount);
}
void Merge(int source[],int result[],int size,int n)
{
　　int lb1,lb2,ub1,ub2,p,i,j;
　　lb1=0;
　　p=0;
　　while((lb1+size)<n)
　　{
　　　　compCount++;
　　　　lb2=lb1+size;
　　　　ub1=lb2-1;
　　　　if((lb2+size-1)>n)
　　　　　 { ub2=n-1; compCount++; shiftCount++;}
　　　　else
　　　　　 {ub2=lb2+size-1; compCount++; shiftCount++;}
　　　　i=lb1;
　　　　j=lb2;
　　　　while((i<=ub1)&&(j<=ub2))
　　　　　　{
　　　　　　　　compCount++;compCount++;
　　　　　　　　if(source[i]<=source[j])
　　　　　　　　　　{result[p++]=source[i++]; shiftCount++; compCount++;}
　　　　　　　　else
　　　　　　　　　　{result[p++]=source[j++]; shiftCount++; compCount++;}
　　　　　　}
　　　　while(i<=ub1)
　　　　　　{result[p++]=source[i++]; shiftCount++; compCount++;}
　　　　while(j<=ub2)
　　　　　　{result[p++]=source[j++]; shiftCount++; compCount++;}
　　　　lb1=ub2+1;
　　}
　　i=lb1;
　　while(p<n)
　　　 {compCount++; result[p++]=source[i++];shiftCount++;}
}
void Mergesort(list *L)
{
　　int n=(*L).length;
　　int s=1;
　　int *temp=(int *)malloc(n*sizeof(int));
　　compCount=shiftCount=0;
　 
　　if (temp==NULL)
　　{
　　　　printf("out of memory");
　　　　return;
　　}
　　while(s<n)
　　{
　　compCount++;
　　Merge((*L).key,temp,s,n);
　　　　s*=2;
　　Merge(temp,(*L).key,s,n);
　　　　s*=2;
　　}
　　compCount++;
}
void domerge(list L,list *LM,float *timemerge)/*MUST add an "getch"!!*/
{
　　clock_t start,end;
　　start=clock();
　　Mergesort(&L);
　 
　　end=clock();
　　(*LM)=L;
　　*timemerge=(end-start)/CLK_TCK;
　 
　　printf("\nMERGESORT COST TIME :%f SECONDS.",*timemerge);
　　printf("Compare %d times.Shfit %d times.\n",compCount,shiftCount);
}
main()
{
　　list L,LS,LQ,LH,LM;
　　int LOCK3=0,LOCK4=0,LOCK5=0,RUN=1,LOCK41=0,LOCK42=0,LOCK43=0,LOCK44=0;
　　int comd,r;
　　float timeshell,timequick,timeheap,timemerge;
　 
　　while(RUN==1)
　　{
start:
　　　　menu(&comd);
　　　　switch (comd)
　　　　{
　　　　　　case 1:
　　　　　　　　create(&L);
　　　　　　　　LOCK3=1;
　　　　　　　　break;
　　　　　　case 2:
　　　　　　　　import(&L);
　　　　　　　　LOCK3=1;
　　　　　　　　goto start;
　　　　　　case 3:
　　　　　　　　if(LOCK3==0) goto start;
　　　　　　　　menusort(&comd);
　　　　　　　　LOCK4=1;
　　　　　　　　LOCK5=1;
　　　　　　　　switch (comd)
　　　　　　　　{
　　　　　　　　 case 1:
　　　　　　　　　　LOCK41=1;
　　　　　　　　　　shell(L,&LS,&timeshell);
　　　　　　　　　　printf("\n PRESS ANY KEY TO RETURN MAIN MENU... \n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 2:
　　　　　　　　　　LOCK42=1;
　　　　　　　　　　quick(L,&LQ,&timequick);
　　　　　　　　　　printf("\n PRESS ANY KEY TO RETURN MAIN MENU... \n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 3:
　　　　　　　　　　LOCK43=1;
　　　　　　　　　　heap(L,&LH,&timeheap);
　　　　　　　　　　printf("\n PRESS ANY KEY TO RETURN MAIN MENU... \n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 4:
　　　　　　　　　　LOCK44=1;
　　　　　　　　　　domerge(L,&LM,&timemerge);
　　　　　　　　　　printf("\n PRESS ANY KEY TO RETURN MAIN MENU... \n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 5:
　　　　　　　　　　LOCK41=1;
　　　　　　　　　　LOCK42=1;
　　　　　　　　　　LOCK43=1;
　　　　　　　　　　LOCK44=1;
　　　　　　　　　　shell(L,&LS,&timeshell);
　　　　　　　　　　quick(L,&LQ,&timequick);
　　　　　　　　　　heap(L,&LH,&timeheap);
　　　　　　　　　　domerge(L,&LM,&timemerge);
　　　　　　　　　　printf("\n PRESS ANY KEY TO RETURN MAIN MENU... \n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 6:
　　　　　　　　　　goto start;
　　　　　　　　}
　　　　　　case 4:
　　　　　　　　if(LOCK4==0) goto start;
　　　　　　　　menushow(&comd);
　　　　　　　　switch(comd)
　　　　　　　　{
　　　　　　　　 case 1:
　　　　　　　　　　if(LOCK41==0) goto start;
　　　　　　　　　　for (r=1;r<=LS.length;r++)
　　　　　　　　　　　　 printf("%d",LS.key[r]);
　　　　　　　　　　printf("\n PRESS ANY KEY TO RETURN MAIN MENU... \n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 2:
　　　　　　　　　　if(LOCK42==0) goto start;
　　　　　　　　　　for (r=1;r<=LQ.length;r++)
　　　　　　　　　　　　 printf("%d",LQ.key[r]);
　　　　　　　　　　printf("\n PRESS ANY KEY TO RETURN MAIN MENU... \n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 3:
　　　　　　　　　　if(LOCK43==0) goto start;
　　　　　　　　　　for (r=1;r<=LH.length;r++)
　　　　　　　　　　　　 printf("%d",LH.key[r]);
　　　　　　　　　　printf("\n PRESS ANY KEY TO RETURN MAIN MENU... \n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 4:
　　　　　　　　　　if(LOCK44==0) goto start;
　　　　　　　　　　for (r=1;r<=LM.length;r++)
　　　　　　　　　　　　 printf("%d",LM.key[r]);
　　　　　　　　　　printf("\n PRESS ANY KEY TO RETURN MAIN MENU... \n");
　　　　　　　　　　getch();
　　　　　　　　　　goto start;
　　　　　　　　 case 6:
　　　　　　　　　　goto start;
　　　　　　　　}
　　　　　　case 5:
　　　　　　　　if(LOCK5==0) goto start;
　　　　　　　　menusave(&comd);
　　　　　　　　switch (comd)
　　　　　　　　{
　　　　　　　 
　　　　　　　　　　case 1:
　　　　　　　　　　　　if(LOCK41==0) goto start;
　　　　　　　　　　　　save(LS);
　　　　　　　　　　　　break;
　　　　　　　　　　case 2:
　　　　　　　　　　　　if(LOCK42==0) goto start;
　　　　　　　　　　　　save(LQ);
　　　　　　　　　　　　break;
　　　　　　　　　　case 3:
　　　　　　　　　　　　if(LOCK43==0) goto start;
　　　　　　　　　　　　save(LH);
　　　　　　　　　　　　break;
　　　　　　　　　　case 4:
　　　　　　　　　　　　if(LOCK44==0) goto start;
　　　　　　　　　　　　save(LM);
　　　　　　　　　　　　break;
　　　　　　　　　　case 6:
　　　　　　　　　　　　break;
　　　　　　　　　　　 
　　　　　　　　}
　　　　　　　　break;
　　　　　　case 6:
　　　　　　　　exit(0);
　　　　}
　 
　　}　 
　 
}

时间： 2024-09-08 14:10:47

排序算法比较程序的相关文章

关于希尔排序算法的程序问题

问题描述 关于希尔排序算法的程序问题 源程序为 void shellsort3(int a[], int n) { int i, j, gap; for (gap = n / 2; gap > 0; gap /= 2) for (i = gap; i < n; i++) for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap) Swap(a[j], a[j + gap]); } 如果修改为: void shel

各种排序算法小结

各种排序算法小结 [watermark] 排序算法是一种基本并且常用的算法.由于实际工作中处理的数量巨大,所以排序算法 对算法本身的速度要求很高. 而一般我们所谓的算法的性能主要是指算法的复杂度,一般用O方法来表示.在后面我将 给出详细的说明. 对于排序的算法我想先做一点简单的介绍,也是给这篇文章理一个提纲. 我将按照算法的复杂度,从简单到难来分析算法. 第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*N)(因为没有 使用word,所以无法打出上标和下标). 第二部分是高级

图解程序员必须掌握的Java常用8大排序算法_java

这篇文章主要介绍了Java如何实现八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序,分享给大家一起学习. 分类1)插入排序(直接插入排序.希尔排序) 2)交换排序(冒泡排序.快速排序) 3)选择排序(直接选择排序.堆排序) 4)归并排序 5)分配排序(基数排序) 所需辅助空间最多:归并排序 所需辅助空间最少:堆排序 平均速度最快:快速排序 不稳定:快速排序,希尔排序,堆排序. 先来看看8种排序之间的关系: 1.直接插入排序 (1)基本思想:

详解计数排序算法及C语言程序中的实现_C 语言

关于计数排序算法 当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 Θ(n + k).计数排序不是比较排序,排序的速度快于任何比较排序算法. 由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量内存.计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名.但是,计数排序可以用在基数排序中的算法来排序数据范围很大的数组. 算法的步骤如下: 找出待排序的数组中最大

PHP 四种基本排序算法的代码实现(1)

许多人都说算法是程序的核心,算法的好坏决定了程序的质量.作为一个初级phper,虽然很少接触到算法方面的东西.但是对于基本的排序算法还是应该掌握的,它是程序开发的必备工具.这里介绍冒泡排序,插入排序,选择排序,快速排序四种基本算法,分析一下算法的思路. 前提:分别用冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中的值按照从小到大的顺序进行排序. $arr(1,43,54,62,21,66,32,78,36,76,39); 1. 冒泡排序 思路分析:在要排序的一组数中,对当前还未排好的序

桶排序算法

桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里.每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序).桶排序是鸽巢排序的一种归纳结果.当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n)).但桶排序并不是比较排序,他不受到 O(n log n) 下限的影响. 本文地址:http://www.cnblogs.com/archimedes/p/bucket-sort-algorithm.html

常见的五类排序算法图解和实现（多关键字排序：基数排序以及各个排序算法的总结）

基数排序思想 完全不同于以前的排序算法,可以说,基数排序也叫做多关键字排序,基数排序是一种借助"多关键字排序"的思想来实现"单关键字排序"的内部排序算法. 两种方式: 1.最高位优先,先按照最高位排成若干子序列,再对子序列按照次高位排序 2.最低位优先:不必分子序列,每次排序全体元素都参与,不比较,而是通过分配+收集的方式. 多关键字排序 例:将下表所示的学生成绩单按数学成绩的等级由高到低排序,数学成绩相同的学生再按英语成绩的高低等级排序.        第一个关键

封装的变化之排序算法中的封装

封装|排序|算法 设想这样一个需求,我们需要为自己的框架提供一个负责排序的组件.目前需要实现的是冒泡排序算法和快速排序算法,根据"面向接口编程"的思想,我们可以为这些排序算法提供一个统一的接口ISort,在这个接口中有一个方法Sort(),它能接受一个object数组参数.对数组进行排序后,返回该数组.接口的定义如下: public interface ISort{ void Sort(ref object[] beSorted);} 其类图如下: 然而一般对于排序而言,排列是有顺序之

排序算法

排序|算法 算法是程序设计的精髓,程序设计的实质就是构造解决问题的算法,将其解释为计算机语言. 在这里您可以了解到: 算法定义 伪代码的使用 算法的复杂性 算法设计策略 常用算法 这里所有的算法都以一种类似Pascal语言的伪代码描述,请参阅伪代码的使用. 新增内容 关于数论的算法--数论基本知识(May 6, 2001)动态规划重新整理 (January 15, 2001)图的深度优先遍历 (January 21, 2001) 图的广度优先遍历 (January 21, 2001)图的拓扑排序