算法设计与分析实验报告 - 模板

实实 验验 报报 告告 2016 2017 学年学年 第一学期 第一学期 学生姓名周文超班级学号B14041527 学院 系 计算机学院 软件学院 专 业软件工程 课程名称算法分析与设计 实验名称分治策略 实验时间2016年10月18日 指导单位计算机学院软件教学中心 指导教师季一木 实实 验验 报报 告告 实验名称实验名称分治策略指导教师指导教师季一木 实验类型实验类型验证实验学时实验学时 2 实验时间实验时间2016 10 18 一 一 实验目的和任务实验目的和任务 1 理解分治法的算法思想 阅读实现书上已有的部分程序代码并完善 程序 加深对分治法的算法原理及实现过程的理解 2 用分治法实现一组无序序列的两路合并排序和快速排序 要求清楚 合并排序及快速排序的基本原理 编程实现分别用这两种方法将输入的一 组无序序列排序为有序序列后输出 二 二 实验环境实验环境 实验设备实验设备 算法设计与分析课本 笔记本电脑 VC 6 0 三 实验原理及内容三 实验原理及内容 包括操作过程 结果分析等 实验原理实验原理 运用分治法 无序 部分有序 整体有序 归并排序中 分 与 合 的过程是结合在一起的 即每一趟都在做 分 与 合 的工作 并不是先 分 完再 合 基本程序基本程序 一 两路合并排序 include class SortableList public SortableList int mSize 构造函数 maxSize mSize l new int maxSize n 0 SortableList delete l 析构函数 void Input void Merge int left int mid int right void MergeSort void MergeSort int left int right void Output private int l 动态生成一维数组 int maxSize 线性表的最大表长 int n 线性表的实际长度 void SortableList Input for int i 0 i l i n void SortableList Merge int left int mid int right int temp new int right left 1 int i left j mid 1 k 0 while i mid else temp k l j while i mid temp k l i while j right temp k l j for i 0 k left k right l k temp i void SortableList MergeSort MergeSort 0 n 1 void SortableList MergeSort int left int right if left right 若序列的长度超过 1 则划分成两个子序列 int mid left right 2 将待排序的序列一分为二 MergeSort left mid 对左序列排序 MergeSort mid 1 right 对右序列排序 Merge left mid right 将两个有序子序列合并成一个有序序列 void SortableList Output for int i 0 i maxSize i cout l i void main SortableList l 10 cout 请输入 10 个数 endl l Input l MergeSort cout 排序后是 endl l Output 二 快速排序 include class SortableList public SortableList int mSize 构造函数 maxSize mSize l new int maxSize n 0 SortableList delete l 析构函数 void Input void Swap int i int j int Partition int left int right void QuickSort int left int right void QuickSort void Output private int l 动态生成一维数组 int maxSize 线性表的最大表长 int n 线性表的实际长度 void SortableList Input for int i 0 i l i n void SortableList Swap int i int j int c l i l i l j l j c int SortableList Partition int left int right 前置条件 left right int i left j right 1 do do i while l i l left if i j Swap i j while i j Swap left j return j void SortableList QuickSort QuickSort 0 n 1 void SortableList QuickSort int left int right if left right 当序列长度大于 1 时 需进行分割 int j Partition left right 对 left right 范围内的序列进行分划 QuickSort left j 1 对左子序列实施快速排序 QuickSort j 1 right 对右子序列实施快速排序 void SortableList Output for int i 0 i maxSize i cout l i void main SortableList l 10 cout 请输入 10 个数 endl l Input l QuickSort cout 排序后是 endl l Output 实验结果实验结果 两路合并排序 快速排序 六 实验小结六 实验小结 包括问题和解决方法 心得体会等 合并排序的基本运算是把两个或多个有序序列合并成一个有序