攀枝花学院实验报告
实验名称：算法设计与分析课程实验实验内容：比较排序算法的效率实验日期：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; j < num.length - i; j++) {
if (num[j] > num[j + 1]) {
// 交换相邻两个数
swap(num, j, j + 1);
}
}
}
}
//交换数组元素
void swap(Integer[] data, int j, int i) {
int temp;
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
public static void main(String args[]) throws FileNotFoundException {
File file = new File("d:\\sort.txt");
PrintWriter writer = new PrintWriter(file);
sort sort = new sort();
final int N =200;
Random rdm = new Random();
Integer[] num = new Integer[N];
//生成随机数并存入到数组num中
for (int i = 0; i < num.length; i++) {
num[i] = rdm.nextInt(5000) + 1;
}
//输出到文件中
writer.append("随机生成的"+N+"个元素的原始数组为：");
for(int i = 0;i writer.append(Integer.toString(num[i])+ " "); writer.flush(); } long begin = System.currentTimeMillis(); sort.quicksort(num, 0, num.length - 1); long end = System.currentTimeMillis(); writer.append("\t\t" + "快速排序后的数组为："); writer.append("快速排序总共用时：" + (end - begin) + "毫秒 "); for (int j = 0; j < num.length; j++) { writer.append(Integer.toString(num[j]) + " "); writer.flush(); } long t1 = System.currentTimeMillis(); sort.MergeSort(num, 0, num.length - 1); long t2 = System.currentTimeMillis(); writer.append("\t\t合并排序后的数组："); writer.append("合并排序总共用时：" + (t2 - t1) + "毫秒 "); for (int j = 0; j < num.length; j++) { writer.append(Integer.toString(num[j]) + " "); writer.flush(); } long s1 = System.currentTimeMillis(); sort.bubbleSort(num); long s2 = System.currentTimeMillis(); writer.append("\t\t冒泡排序后的数组："); writer.append("冒泡排序总共用时：" + (s2 - s1) + "毫秒 "); for (int k = 0; k < num.length; k++) { writer.append(Integer.toString(num[k]) + " "); writer.flush(); } } } 程序实验结果如下图所示： 由实验结果可知，在这进行比较的三种排序算法中快速排序是最有效率的算法，其次是合并排序，然后是冒泡法。 宁波工程学院电信学院计算机教研室 实验报告 课程名称：算法设计与分析 实验项目：实验一：分治法 指导教师：苏日娜 实验位置：计算机中心二楼 姓 名：李勇 班 级：计科网络 学 号：09401010440 日 期：20##-10-18 一、实验目的 通过上机实验，要求掌握分治法算法的问题描述、算法设计思想、程序设计和算法复杂性分析等。 二、实验环境 电信楼2楼机房 三、实验内容 1、 用分治法算法解最接近点对问题 （1）问题的描述 在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一，我们着重考虑平面上的最接近点对问题，最接近点对问题主要要解决的是给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小，严格地说，最接近点对可能多于1对，为了简单起见，这里只限于找其中的一对。 （2）算法设计思想 这个问题看似比较容易解决，通常我们想到的是我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n2)的计算时间。在问题的计算复杂性中我们可以看到，该问题的计算时间下界为Ω(nlogn)。这个下界引导我们去找问题的一个θ(nlogn)算法。这个问题会让我们很自然地想到用分治法来解决，我们考虑将所给的平面上n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，•然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足：T(n)=2T(n/2)+O(n2)。 （3）程序设计 主要的算法如下： 求点的x坐标的中位数mid： int minX=(int)Double.POSITIVE_INFINITY; int maxX=(int)Double.NEGATIVE_INFINITY;//用强制性装换将一个很大浮点数给变量maxx. for(int i=0;i { if(S[i].getX() minX=S[i].getX(); if(S[i].getX()>maxX) maxX=S[i].getX();//通过for循环语句及if语句将值给minx及maxx. } int mid=(minX+maxX)/2; 以mid为界把S中的点分为两组分别存放在范型数组列表point1和point2中： ArrayList ArrayList //范型数组名ArrayList定义两个变量，然后把s中的点存放在这两个变量中。 for(int i=0;i {//for语句控制出口，通过if语句将适合的点分别存放在变量中。 if(S[i].getX()<=mid) point1.add(S[i]); else point2.add(S[i]); } 求S1中点的最近对及其距离并打印输出结果： double minDist1=Double.POSITIVE_INFINITY; int indexI1=0; int indexJ1=0; for(int i=0;i {//用for语句控制循环然后将值给对象求值 for(int j=i+1;j { Double d=Math.sqrt(Math.pow((S1[i].getX()-S1[j].getX()),2)+Math.pow((S1[i].getY()-S1[j].getY()),2));//用Math.sqrt（）用法求出距离给d. if(d { minDist1=d; indexI1=i; indexJ1=j; } } } System.out.println("The closest pair in S1 is: "+"("+S1[indexI1].getX()+","+S1[indexI1].getY()+")"+ "and("+S1[indexJ1].getX()+","+S1[indexJ1].getY()+")"+",and the distance is "+minDist1); 求S2中点的最近对及其距离并打印输出结果： double minDist2=Double.POSITIVE_INFINITY; int indexI2=0; int indexJ2=0; for(int i=0;i { for(int j=i+1;j { double d=Math.sqrt(Math.pow((S2[i].getX()-S2[j].getX()),2)+Math.pow((S2[i].getY()-S2[j].getY()),2)); if(d { minDist2=d; indexI2=i; indexJ2=j; } } } System.out.println("The closest pair in S2 is: "+"("+S2[indexI2].getX()+","+S2[indexI2].getY()+")"+ "and("+S2[indexJ2].getX()+","+S2[indexJ2].getY()+")"+",and the distance is "+minDist2); double d1=Math.min(minDist1,minDist2); 求出S1和S2中点的横坐标离小于d1的所有点分别存在P1[]和P2[]中： ArrayList ArrayList for(int i=0;i { if((mid-S1[i].getX()) pp1.add(S1[i]); } for(int i=0;i { if((S2[i].getX()-mid) pp2.add(S2[i]); } Point[] P1=new Point[pp1.size()]; Point[] P2=new Point[pp2.size()]; pp1.toArray(P1); pp2.toArray(P2); 求解P1和P2两者之间可能的最近对距离： double d2=Double.POSITIVE_INFINITY; for(int i=0;i { for(int j=0;j { if(Math.abs(P1[i].getY()-P2[j].getY()) { double temp=Math.sqrt(Math.pow((P1[i].getX()-P2[j].getX()),2)+Math.pow((P1[i].getX()-P2[j].getX()),2)); if(temp d2=temp; } } } 打印输出最后求出的结果，最近的是哪两个点： System.out.print("The points in P1 are:"); for(int i=0;i System.out.print("("+P1[i].getX()+","+P1[i].getY()+") ");//通过 for语句循环和判断，输出在其中一个变量中的点对。 System.out.println(); System.out.print("The points in P2 are:"); for(int i=0;i System.out.print("("+P2[i].getX()+","+P2[i].getY()+") "); System.out.println(); System.out.println("d2="+d2);//输出通过比较后较短的那个点 double minDist=Math.min(d1,d2); System.out.println("the closest distance is"+minDist); } （4）数据输入和结果输出 （5）算法复杂性分析 这个问题考虑将所给的平面上n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足：T(n)=2T(n/2)+O(n2) 。 四、实验心得与小结 通过这次实验，对分治法有了更进一步的了解，最初老师在上这一节课程的时候，感觉比较抽象，有点难懂，不过在这次实验后，觉得不是那么的抽象了，现在回头去看其他的例子也觉得容易了许多，不过在最初做这个实验的时候，不知道该如何下手，用了一节课的时间看书上的例子和在网上查询相关的知识，最后有了一些印象后才着手写程序，虽然这次实验花了很长的时间，但是觉得是很值得的，因为不但对上课的知识有了更深的理解，还让我在写程序过程中，复习了很多的java知识，对编程是很有帮助的，这次实验整体上是很不错的，多练习后我相信以后会做得更好。 五、指导教师成绩评定：
第二篇：《算法设计与分析》实验报告一
