C语言课程设计---各种排序算法的设计和分析

1、C语言课程设计各种排序算法的设计和分析华中科技大学文华学院11级课程设计华中科技大学文华学院数据结构课程设计学号：学部：信息科学与技术学部专业：班级：题目：各种排序算法的设计和分析教师:2013年03月07日一.课程设计报告的内容1. 设计题目2. 运行环境（软、硬件环境）3. 算法设计的思想4. 算法的流程图5. 算法设计分析6. 源代码7. 运行结果分析&收获及体会二数据结构课程设计题目各种排序算法的设计和分析1.设计题目、需求分析利用随机函数产生N个随机整数（N=4000）,利用直接插入排序、折 半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排 序方法（可添加其它排序方法

2、）进行排序（结果为由小到大的顺序），并统 计每一种排序所耗费的时间。把排序花的时间排在表格里面。（2人程序的主要功能1用户输入任意个数，产生相应的随机数2用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排 序、快速排序、选择排序、堆排序、基数排序）的一种3 程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。 （3）.程序运行平台Visual C+ 6.0 版本、数据结构（5）、算法及时间复杂度（一）各个排序是算法思想：（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。(2) 折半插入排序：插入排序的基本插入是在一个有序表中进行查

3、找和插 入，这个查找可利用折半查找来实现，即为折半插入排序。(3) 起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比 较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记 录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比 较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到 最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录 进行同样操作。一共要进行N-1趟起泡排序。(4) 快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部 分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分 记录继续进行排序，己达到整个序列有序。(5)

4、 选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选出关键 字最小的记录，并和第I (1=I=N)个记录交换。(6) 堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束。(7) 基数排序：按最低位优先法先对低位关键字进行排序，直到对最高位关键字排序为止，经过若干次分配和收集来实现排序(二)时间复杂度分析排序算法最差时间时间复杂度是否稳定？插入排序0(n2)0(n2)稳定冒泡排序0(n2)0(n2)稳定快速排序0(n2)0(n*log2n)不稳定选择排序0(

5、n2)0(n2)稳定堆排序0(n*log2n)0(n*log2n)不稳定基数排序0(n*log2n)0(n2)稳定4000个数据的时间比较:算法名称用时直接插入排序0.0623ZI折半插入排序0.047|起泡排序30.188快速排序0. 000选择排序0. 078堆排序 10. 000L基数排序|0. 000(三)源代码：代码如下：#include #include #include #define N 4000 void InsertSort() 第一个插入排序 int ij,t;int aN; for(i=0;iN;i+)ai=(int)rand();printf(n%dn,ai);pri

6、ntf(HnH); for(i=l;i=0&tat;j“)aj+l=aj; aj+l=t;for(i=0;iN;i+)printf插入排序的程序:%dnn9ai);void BInsertSort()/M二个，折半插入排序int i=0J=0Jow=0,high=09m=0;for(i=0;iN;i+)ai=(int)rand();printf(n%dfai); printf(nnn);for(i=2;i=N ;+i)LO=Li;low=l;high=i-l; while(low=high) m=(low+high)/2; if(LOLm) high=m-l;elselow=m+l;forG=

7、i-l;L0LU;-j)Lj+l=Lj;/iB 录后移Lhigh+1=LO; 插入 void BubbleSort()第三个,冒泡排序int iJJ；int aN;for(i=0;iN;i+)ai=(int)rand(); printf(H%d fai);printf(Hnn); for(i=0;iN;i+)foro;jANx.;j+) 亠 inamva 口+1)H吕；aDlla 口+1；旦 i+llrl;prs-ff(二郵圧3W普誓逊淨dinf Quicksor6vwI94v爭崗血還inf mid;inf daNl;inflow;inf high;for(i=o;AN;i+)亠aill(im

8、)rand9prinff(二 d 二邑 i)；primfrw)；dafasHdafa 口 ow; midudafa 口 OWJ whiAlow A high)亠whiAaow A high) 081 (dafanlighvn mid)-high；data low=da ta high;while(low high) & (datalow mid) +low;datahigh=datalow;datalow=data0;return low;void ChooseSort()第五个，选择排序intint aN;for(i=0;iN;i+) ai=(int)rand();printf(n%dn,a

9、i);printf(nnn);for(i=0;i10;i+)k=i;for(j=i+l;j* 济誓迦 亠im s；inf i;im rz； reNrlxh for(i=o;AN;i+)ailr(im)rand()； prinff(二 d vm)； for(i=2 许 s;i+l=N;if 2)if(穴 N rmcs+1)+;ifsOYm)break;rEHrE;s;rs=rO; return 1;typedef struct node int key; node *next;JRecType;Status RadixSort(Sqlist L)第七个，基数排序 intRecType *p，*s

10、，*q，*head10，*tail10;for(i=l ;ikey=L.ri;if(i=l)q=s;P=s; t+;else q-next=s; Q=s； t+;q-next=NULL; d=l;while(n0)for(j=0;jkey/d; k=k%10; if(headk=NULL) headk=p; tailk=p;elsetailk-next=p; tailk=p; p=p-next;p=NULL;for(j=0;jnext=headj; q=tailj; q-next=NULL;d=d*10;n=0; m=l; while(mkey; i+； p=p-next;return OK;

11、主函数 void main()printf(n请输入 figure： n); scanf(n %df&figure);clock_t start, finish; 定义 clock_t 用于计时 double duration;printf(Hn2 2 “ rjrj rjrj rj rj rjrj rjrjrj rj rj rjprintf(Hnj;算法n“);printf(H排序比较系统printf(nn“)；printf(H 2 “2 t# ! 上 2 2 rjrj rj rj rj rjrjrj rj rj rj rj rj rj rj rjrj rjrj rj rj rj rj rj

12、rj rjprintf（ff以下是各个排序算法的代号：nnn）;一、直接插入排序printf(H printf(H printf(n printf(n printf(n printf(H printf(n二、折半插入排序三、冒泡排序3)；W)；W)；快速排序Z）；五、选择排序W）；六、堆排序Z）；七、基数排序5）；printf（n八、退出该系统nnj;switch(figure) case 1:/直接插入排序start=clock();InsertSort(); flnish = clock(); break;case 2:/卅半插入排序start = clock(); BInsertSort

13、(); finish = clock(); break;case 3:/冒泡排序start = clock(); BubbleSort(); Hnish = clock(); break;case 4:/机速排序start = clock(); QuickSort(); Hnish = clock(); break;case 5:/速择排序start = clock(); ChooseSort(); finish = clock(); break;case 6:/薙排序start = clock(); HeapSort(); finish = clock(); break;case 7:/塞数

14、排序start = clock();RadixSort (1); flnish = clockQ;break;case &/直接退出break;duration = (double)(finish - start) / 1000;/瀚出算术时间printf(Hn 本次的时间是：% Ifsecondsn duration);感想体会与总结1、做什么都需要耐心，做设计写程序更需要耐心。一开始的时候，我 写函数写的很快，可是等最后调试的时候发现错误很隐蔽，就很费时间了。 后来我先在纸上构思出函数的功能和参数，考虑好接口之后才动手编，这 样就比较容易成功了。2、做任何事情我决定都应该有个总体规划。之后的工作按照规划逐步 展开完成。对于一个完整的程序设计，首先需要总体规划写程序的步骤， 分块写分函数写，然后写完一部分马上纠错调试。而不是像我第一个程序, 一口气写完，然后再花几倍的时间调试。一步步来，走好