北航计算计软件基础实验三报告.doc

实验报告 实验名称 实验三 冒泡排序和快速排序 班 级 学 号 姓 名 成 绩 实验概述： 【实验目的及要求】 通过编程程序达到熟悉并掌握教材中所介绍的几种排序方法。 【实验原理】 1 . 随机产生20位整数 2 . 输入序列，编写程序，按下列排序方法将序列从小到大排序并输出。 (1) . 冒泡排序 (2) . 快速排序 3 . 纪录每种方法比较次数和移动次数 【实验环境】（使用的软硬件） VC++6.0编译平台和C++语言。 实验内容： 【实验方案设计】 1．用系统自带的库函数rand（）生成20个随机数，并存放在数组randnum中。 2 . 编写两个程序分别进行冒泡排序和快速排序，同时定义move和comp两个变量分别进行移动和比较次数的计数。 3．输出排序后的结果。 【实验过程】（实验步骤、记录、数据、分析） 1 . 产生随机数的函数： void randNum (int* num, int n, int min, int max) { for(int i = 0; i n; i++) { num[i] = rand() % max + min; } } 调用此函数前在main函数中加一句srand((long int)time(0)); 使产生的随机数随时间的变化而变化。此函数将生成的随机数存放在一个数组中。 2. 冒泡排序： void bubbleSort(int* num, int n, int* move, int* comp) { int j = n - 1; while(j 0) { for(int i = 0; i j; i++) { *comp = *comp + 1; // 比较次数+1 if(num[i] num[i+1]) { int temp = num[i]; num[i] = num[i + 1]; num[i + 1] = temp; *move = *move + 1; // 移动次数+1 } } j--; } } 设置两个循环实现冒泡排序的算法，同时每当比较和移动的时候，相应的计数变量要加1。 3 . 快速排序： void quickSort(int* K, int s, int t, int *move, int *comp) { int i, j; if(s t) { i = s; j = t+1; while(1) { do {i++; *comp += 1;} // 比较次数+1 while(!(K[s] = K[i] || i == t)); do {j--; *comp += 1;} // 比较次数+1 while(!(K[s] = K[j] || j == s)); if(i j) swap(K[i], K[j], move); else break; } swap(K[s], K[j], move); quickSort(K, s, j - 1, move, comp); quickSort(K, j + 1, t, move, comp); } } 快速排序的核心思想是将大问题化为小问题，运用到了递归的思想。是一个比较快的排序算法。 4 . 记录： 【结论】 对于产生的20个随机数：64 79 36 66 42 41 41 83 63 30 46 47 94 88 8 87 5 40 76 96 经过排序后得到非递减序列：5 8 3