北京信息科技大学课程设计报告课程名称数据结构课程设计题目排序与查找指导教师赵庆聪设计起止日期设计地点系别信息管理学院专业__信息管理与信息系统_姓名/学号______鲁丹2012012108__b=SelectSort(L);display(L);printf("此排序法关键字比较的次数为:%d\n",b);printf("\n快速排序输出的顺序表为:\n");c=QuickSort(L,1,20);display(L);printf("此排序法关键字比较的次数为:%d\n",c); printf("\n双向起泡法排序输出的顺序表为:\n");d=BubbleSort(L);display(L);printf("此排序法关键字比较的次数为:%d\n",d);}1.#include "stdio.h"2.#include "stdlib.h"3.#include "string.h"4.#include "time.h"5.#include "limits.h"6.#define MAXITEM 10007.typedef int KeyType,ElemType;8.int count1=0,count2=0,count3=0,count4=0,count5=0,count6=0;9.int swap1=0,swap2=0,swap3=0,swap4=0,swap5=0,swap6=0;10.typedef struct rec11.{12. KeyType key;13. ElemType data;14.}sqlist[MAXITEM];15.16.void gennum(sqlist r,sqlist t,int n)17.{18.int i;19. srand((unsigned)time(NULL));20.for(i=1;i<=n;i++)21. { t[i].key=rand()%100;22. r[i].key=t[i].key;23. }24.}25.26.void ini(sqlist r,sqlist t,int n)27.{28.int i;29.for(i=1;i<=n;i++)30. r[i].key=t[i].key;31.}32.33.void BubbleSort(sqlist r,int n)//起泡法r[1]~r[n]34.{35.int i,j;36.struct rec w;37.for(i=1;i<=n-1;i++)38.for(j=n;j>=i+1;j--)39. {40.if(r[j].key<r[j-1].key)41. {42. w=r[j];43. r[j]=r[j-1];44. r[j-1]=w;45. swap1++;46. }47. count1++;48. }49.50.}51.52.53.void InsertSort(sqlist r,int n)//直接插入排序r[1]~r[n]54.{55.int i,j;56.for(i=2;i<=n;i++)57. {58. count2++;59. r[0]=r[i];60. j=i-1;61.while(r[0].key<r[j].key)62. {63. r[j+1]=r[j];64. j--;65. count2++;66. swap2++;67. }68. r[j+1]=r[0];69. swap2++;70. }71.}72.73.void SelectSort(sqlist r,int n)//简单选择排序r[1]~r[n]74.{75.int i,j,k;76.struct rec temp;77.for(i=1;i<=n-1;i++)78. {79. k=i;80.for(j=i+1;j<=n;j++)81.if(r[j].key<r[k].key){k=j;count3++;}82.if(i!=k)83. {84. temp=r[i];85. r[i]=r[k];86. r[k]=temp;87. swap3++;88. }89. }90.}91.92.void QuickSort(sqlist r,int s,int t)//快速排序r[s]~r[t],r[0]空出93.{94.int i=s,j=t;95.if(s<t)96. {97. r[0]=r[s];swap4++;98.do99. {100.while(j>i&&r[j].key>=r[0].key){j--;count4++;} 101.if(i<j)102. {103. r[i]=r[j];104. i++;105. swap4++;106. }107.while(i<j&&r[i].key<=r[0].key){i++;count4++;} 108.if(i<j)109. {110. r[j]=r[i];111. j--;112. swap4++;113. }114. }while(i<j);115. r[i]=r[0];116. swap4++;117. QuickSort(r,s,j-1);118. QuickSort(r,j+1,t);119. }120.}121.122.void ShellSort(sqlist r,int n)//希尔排序r[1]~r[n]123.{124.int i,j,gap;125.struct rec x;126. gap=n/2;127.while(gap>0)128. {129.for(i=gap+1;i<=n;i++)130. {131.132. j=i-gap;133.while(j>0)134.if(r[j].key>r[j+gap].key)135. {136. x=r[j];137. r[j]=r[j+gap];138. r[j+gap]=x;139. j=j-gap;140. count5++;141. swap5++;142. }143.else144. {145. j=0;count5++;146. }147. }148. gap=gap/2;149. }150.}151.152.void sift(sqlist r,int l,int m)153.{154.int i,j;155.struct rec x;156. i=l;157. j=2*i;158. x=r[i];159.while(j<=m)160. {161.if(j<m&&r[j].key<r[j+1].key){j++;count6++;} 162.if(x.key<r[j].key)163. {164. r[i]=r[j];165. i=j;166. j=2*i;167. count6++;168. swap6++;169. }170.else {j=m+1;count6++;}171. }172. r[i]=x;173.}174.void HeapSort(sqlist r,int n)//堆排序r[1]~r[n]175.{176.int i;177.struct rec m;178.for(i=n/2;i>=1;i--)sift(r,i,n);179.for(i=n;i>=2;i--)180. {181. m=r[i];182. r[i]=r[1];183. r[1]=m;184. swap6++;185. sift(r,1,i-1);186. }187.}188.189.void main()190.{191.192.int k,n,a;193. sqlist r,t;194. printf(" ***************************************\n");195. printf(" * *\n");196. printf(" * * 内部排序算法的性能分析 * *\n");197. printf(" * *\n");198. printf(" ***************************************\n\n");199.200. printf("-----------------*-------------------------------------*----------------\n"); 201. printf("**是否执行程序**\n");202. printf("(是) 按 1 键, (否) 按 0 键\n");203. printf(" 按键为：");204. scanf("%d",&a);205. printf("-----------------*-------------------------------------*----------------\n"); 206.207.while(a==1)208. {printf("**请输入要排序的数据的个数：");209. scanf("%d",&n);210.211. gennum(r,t,n);212. printf("\n");213.214. printf("**随机产生的最初顺序是:\n");215.for(k=1;k<=n;k++)216. { printf("%3d",t[k].key);217.if(k%20==0)218. printf("\n");219. }220. printf("\n");221. BubbleSort(r,n);222. printf("\n**排序之后的顺序是:\n");223.for(k=1;k<=n;k++)224. { printf("%3d",r[k].key);225.if(k%20==0)226. printf("\n");227. }228. printf("\n\n");229. printf("-------------------------------*分析结果*-------------------------------\n\n"); 230. printf(" **起泡排序**\n");231. printf(" 比较的次数是: %d,移动的次数是: %d\n\n",count1,swap1);232.233. ini(r,t,n);234. InsertSort(r,n);235. printf(" **直接插入**\n");236. printf(" 比较的次数是: %d,移动的次数是: %d\n\n",count2,swap2);237.238. ini(r,t,n);239. SelectSort(r, n);240. printf(" **简单选择排序**\n");241. printf(" 比较的次数是: %d,移动的次数是: %d\n\n",count3,swap3);242.243. ini(r,t,n);244. QuickSort(r,1,n);245. printf(" **快速排序**\n");246. printf(" 比较的次数是: %d,移动的次数是: %d\n\n",count4,swap4);247.248. ini(r,t,n);249. ShellSort(r,n);250. printf(" **希尔排序**\n");251. printf(" 比较的次数是: %d,移动的次数是: %d\n\n",count5,swap5);252.253. ini(r,t,n);254. HeapSort(r,n);255. printf(" **堆排序**\n");256. printf(" 比较的次数是: %d,移动的次数是: %d\n\n",count6,swap6);257.258. printf("-----------------*-------------------------------------*----------------\n"); 259. printf("**是否继续执行程序**\n");260. printf(" (是) 按 1 键, (否) 按 0 键\n");。