1 北京信息科技大学课程设计报告课程名称 数据结构课程设计 题 目 排序与查找 指导教师 设计起止日期 设计地点 系 别 信息管理学院 专 业 _信息管理与信息系统_姓名/学号_鲁丹 _ 2 1.课程实践目的：通过本实践使学生对各类排序算法有更深入的了解，在实际应用中学会使用排序算法解决具体问题。2.课程实践内容：a) 随机产生 20 个 0100 之间的整数，允许有重复b) 分别利用直接插入排序、直接选择排序、快速排序、双向起泡排序对这 20 个数进行排序（递增递减均可） ，并统计在各种排序方法中关键字的比较次数，最后输出各类排序方法的排序结果及关键字的比较次数。提示：双向起泡排序是对标准起泡排序算法的改进，该方法第一次自上而下进行“起泡” ，使最大元素“下沉”到底，第二次自下而上进行“起泡” ，使最小元素“上浮”到顶，之后又重复上述过程，每趟起泡后都会相应缩小下一趟的起泡排序区间，直至排序完成。起泡期间可以通过对某趟“起泡”的“最后交换位置”进行记忆，以尽可能快地缩短下一趟的“起泡”区间。c) 用折半查找法在前面的已排好序的数据表上查找，是否有此数，如有，输出其序号。如没有，在屏幕给出提示信息。3.实践步骤：#include#include#include#define N 100#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10 3 #define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef structElemType *elem;int length;int listsize;List;Status InitList(List &L)L.elem=(ElemType * ) malloc(LIST_INIT_SIZE * sizeof(ElemType);L.length = 0;L.listsize=LIST_INIT_SIZE;return OK;/InitListvoid Create(List &L, int n) 4 int i;srand(time(NULL);for(i=0;i=L.elemj) 5 m+;else m+;while(j=0)&(ti&L.elemj=L.elem0)j-;count4+; if(ii;j-)if(L.elemj-1L.elemj)flag=1;int m;m=L.elemj;L.elemj=L.elemj-1;L.elemj-1=m;t+;else t+;return t; void display(List L) 10 int i;for(i=0;i=i+1;j-) 39. 40. if(rj.keyi 101. if(i0) 128. 129. for(i=gap+1;i0) 134. if(rj.keyrj+gap.key) 135. 136. x=rj; 137. rj=rj+gap; 15 138. rj+gap=x; 139. j=j-gap; 140. count5+; 141. swap5+; 142. 143. else 144. 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=ri; 159. while(j=1;i-)sift(r,i,n); 16 179. for(i=n;i=2;i-) 180. 181. m=ri; 182. ri=r1; 183. r1=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( *nn); 199. 200. printf(-*-*-n); 201. printf(*是否执行程序*n ); 202. printf(是) 按 1 键, (否) 按 0 键n); 203. printf( 按键为：); 204. scanf(%d, 205. printf(-*-*-n); 206. 207. while(a=1) 208. printf(*请输入要排序的数据的个数： ); 209. scanf(%d, 210. 211. gennum(r,t,n); 212. printf(n); 213. 214. printf(*随机产生的最初顺序是 :n); 215. for(k=1;k=n;k+) 216. printf(%3d,tk.key); 217. if(k%20=0) 218. printf(n); 219. 17 220. printf(n); 221. BubbleSort(r,n); 222. printf(n*排序之后的顺序是:n); 223. for(k=1;k=n;k+) 224. printf(%3d,rk.key); 225. if(k%20=0) 226. printf(n); 227. 228. printf(nn); 229. printf(-*分析结果 *-nn); 230. printf( *起泡排序*n ); 231. printf( 比较的次数是: %d,移动的次数是: %dnn,count1,swap1); 232. 233. ini(r,t,n); 234. InsertSort(r,n); 235. printf( *直接插入*n ); 236. printf( 比较的次数是: %d,移动的次数是: %dnn,count2,swap2); 237. 238. ini(r,t,n); 239. SelectSort(r, n); 240. printf( *简单选择排序*n); 241. printf( 比较的次数是: %d,移动的次数是: %dnn,count3,swap3); 242. 243. ini(r,t,n); 244. QuickSort(r,1,n); 245. printf( *快速排序*n ); 246. printf( 比较的次数是: %d,移动的次数是: %dnn,count4,swap4); 247. 248. ini(r,t,n); 249. ShellSort(r,n); 250. printf( *希尔排序*n ); 251. printf( 比较的次数是: %d,移动的次数是: %dnn,count5,swap5); 252. 253. ini(r,t,n); 254. HeapSort(r,n); 255.