算法分析与设计实验一样本.docx

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
《算法分析与设计》实验报告
专业: 计科 班级: 日期: /04/11 成绩:
学生姓名: 学号: 指导老师:
实验单元一 递归设计
一、 实验题目
实验一 排序
二、 实验目的
熟悉java语言(或C++)的集成开发环境; 经过两种利用分治算法求解的排序算法来加深对递归设计和分治算法的理解。
三、 实验内容
掌握递归算法的概念和基本思想, 分析并掌握排列问题的递归算法。对于一个序列, 使用快速排序算法和归并排序算法对其实现排序。
四、 实验结果( 代码及运行结果)
(一) 快速排序源代码:
public class QuickSort {
public static void main(String[] args) {
int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
print(data);
quickSort(data, 0, data.length - 1); // 调用快速排序方法
System.out.println("排序后的数组: "); // 打印输入函数
print(data);
}
/**
* 交换i、 j位置数组中的内容( 替代了新建临时变量)
*/
public static void swap(int[] data, int i, int j) {
if (i == j) {
return;
}
data[i] = data[i] + data[j];
data[j] = data[i] - data[j];
data[i] = data[i] - data[j];
}
/**
* 快速排序核心方法
*/
public static void quickSort(int[] data, int start, int end) {

if (start >= end) // 排除数组中仅有一个元素的情况
return;
// 以起始索引为分界点
int pivot = data[start];
int i = start + 1;
int j = end;
while (true) {
while (i <= end && data[i] < pivot) {
i++; // 从数组左边第二个元素开始,若小于pivot的元素, 下标加1
}

while (j > start && data[j] > pivot) {
j--; // 从数组最后一个元素开始,凡大于pivot的元素, 下标减1
}

if (i < j) {
// 经过上面的操作, data[i]大于pivot, data[j]小于pivot, 因此交换i、 j中的内容
swap(data, i, j);
} else {
break;
}
}
swap(data, start, j);
print(data);
quickSort(data, start, j - 1); // 递归左子序列
quickSort(data, j + 1, end); // 递归右子序列
}

public static void print(int[] data) {

for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
}

运行结果为:

1.1 快速排序算法运行结果
(二) 归并排序源代码:

public class MergeSortTest {

// 设计count静态全局变量, 计算递归的次数
private static int count = 0;
public static void main(String[] args) {
int[] data = new int[] { 0, 0, 5, 3, 6, 2, 9, 4, 7 };
System.out.print("排序前: \t");
print(data);
mergeSort(data); // 调用归并排序方法
System.out.print("排序后: \t");
print(data);
}
/**
* 归并排序方法mergeSort
*/
public static void mergeSort(int[] data) {
sort(data, 0, data.length - 1);
}
/**
* 排序方法
*/
public static void sort(int[] data, int left, int right) {
if (left >= right) // 如果数组中只有一个元素, 则无须操作。返回空
return;
int center = (left + right) / 2; // 求中间索引
sort(data, left, center); // 1、 左递归
sort(data, center + 1, right); // 2、 右递归
merge(data, left, center, right); // 3、 合并
System.out.print("第" + (count++) + "递归\t");
print(data); // 打印输出数组
}
/**
* 归并方法, 归并前面2个数组已有序, 归并后依然有序
*
* @param data 数组对象
* @param left 左数组的第一个元素的索引
* @param center 左数组的最后一个元素的索引, center+1是右数组第一个元素的索引
* @param right 右数组最后一个元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
int[] temp = new int[data.length]; // 经过new关键字, 在堆上创立临时数组
int middle = center + 1; // 右数组第一个元素索引
int k = left; // k记录临时数组的索引
int tmp = left; // 缓存左数组第一个元素的索引
while (left <= center && middle <= right) {
if (data[left] <= data[middle]) { // 从两个数组中取出最小的放入临时数组
temp[k++] = data[left++];
} else {
temp[k++] = data[middle++];
}
}
while (middle <= right) { // 剩余部分依次放入临时数组( 实际上两个while只会执行其中一个)
temp[k++] = data[middle++];
}
while (left <= center) {
temp[k++] = data[left++];
}
while (tmp <= right) { // 将临时数组中的内容拷贝回原数组中
data[tmp] = temp[tmp++];
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();}}

运行结果:

2.1 归并排序算法运行结果-异常

2.2 异常原因-导入多余的包

2.3 归并排序算法运行正确结果显示

3.1 快速、 归并排序算法文件

五、 实验体会
合并排序: 用分治策略实现对n个元素进行排序的算法。基本思想: 将待排序元素分成大小大致相同的两个子集合, 分别对两个子集合进行排序, 最终将排序好的子集合合并成所要求的排好序的集合。
快速排序: 基于分治策略的另一个排序算法。基本思想: 对于输入的子数组a[p:r], 按以下三个步骤进行排序:
( 1) 分解( Divide) : 以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q],a[q+1:r],使a[p:q-1]中的任何一个元素小于等于a[q], 而a[q+1:r]中任何一个元素大于等于a[q]。下标q在划分过程中确定。
( 2) 递归求解( Conquer) : 利用递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。
( 3) 合并( Merge) : 由于对a[p:q-1]和a[q+1:r]的排序是就地进行的, 因此在a[p:q-1]和a[q+1:r]都已经排好的序后, 不需要执行任何计算,a[p:r]就已经排好序。

心得体会:
学习初衷: 在大三接触这门选修课, 不知道算早还是晚。现实中, 已经面临就业的问题, 其实以前也想过补充自己关于算法方面的知识。可是一直没有挤出时间、 更确切地说拿出勇气去研究一些算法。正好, 在毕业之际, 选了这门课, 经过实验能够更好地掌握关于算法方面的一些基本知识。
实验过程:
实验进行的并不是很顺利, 由于长时间没有编这种有关算法的程序( 或者说是几乎没有编过) , 因此消耗了近一个中午仍旧没有什么进展。虽然自己也写了一百行代码。就如同老师说的那样, 出错率很高, 特别是逻辑上的错误。例如: 数组下表越界、 出程序逻辑太混乱等。
难题解决:
经过复习教材22-26页关于合并、 快速排序算法的概念, 以及在晚上查阅一些资料。自己在eclipse中完成两个小实验。经过这次实验, 自己了解到了归并、 快速排序算法以及分治思想。经过对比学习了归并和快速的异同。虽然没有自己亲手编写出来那份难以抑制的激动, 可是学到了( 熟悉了) 关于算法方面的知识, 进步的我还是很欣慰。
希望经过这门课以及自己按时完成实验, 为自己以后打下一些基础!