算法设计与分析验报告1.doc

攀枝花学院实验报告 实验名称：算法设计与分析课程实验 实验内容：比较排序算法的效率 实验日期：2013.03.26 院系：数学与计算机 姓名：吴永昊 学号：201010804043 同组人： 指导老师：银星 成绩： 一、【目的与任务】 通过算法的程序实现和执行时间测试、并与理论上的结论进行对比分析，深入理解算 法时间复杂度分析中对于输入数据考虑其等价类的意义，理解算法时间复杂度 二、【实验要求：】 要求编程实现将合并算法和快速排序算法以及其他另外一种算法（冒泡、插入、选择）进行比较，数组元素随机生成，最后输出到文件里，然后比较各种排序算法的所用的时间来比较其效率，编程语言不做要求。 三、【实验器材】 Pc 机一台 软件环境：eclipse 或 my eclipse。 编程语言：java. 四、【实验内容】 程序代码如下： import java.io.File; import java.io.FileNotFoundException; import java.io.PrintWriter; import java.util.Random; public class sort { //快速排序 void quicksort(Integer num[], int low, int high) { int i, j, x; if (low high) { // 这个条件用来结束递归 i = low; j = high; x = num[i]; while (i j) { while (i j num[j] x) { j--; // 从右向左找第一个小于x的数 } if (i j) { num[i] = num[j]; i++; } while (i j num[i] x) { i++; // 从左向右找第一个大于x的数 } if (i j) { num[j] = num[i]; j--; } } num[i] = x; quicksort(num, low, i - 1); quicksort(num, i + 1, high); } } //合并排序 void MergeSort(Integer a[], int left, int right) { if (left right) { // 至少需要两个元素 int mid = (left + right) / 2; // 对左侧排序 MergeSort(a, left, mid); // 对右侧排序 MergeSort(a, mid + 1, right); // 合并两段排序数组到数组b中,再拷贝回a中 merge(a, left, mid, right); } } void merge(Integer c[], int left, int mid, int right) { // 合并两段排序数组到数组d中 int d[] = new int[right - left + 1]; int i, j, k = 0; // k为d数组的下标 i = left; j = mid + 1; while (i = mid j = right) { if (c[i] c[j]) { d[k] = c[j]; k++; j++; } else { d[k] = c[i]; k++; i++; } } for (int q = j; q = right; q++) { d[k] = c[q]; k++; } for (int q = i; q = mid; q++) { d[k] = c[q]; k++; } // 将d中数组再拷贝回c中 int pos = left; for (k = 0; k = d.length - 1; k++) { c[pos] = d[k]; pos++; } } //冒泡排序 void bubbleSort(Integer[] num) { // 比较的轮数 for (int i = 1; i num.length; i++) { // 将相邻两个数进行比较，较大的数往后冒泡 for (int j = 0;