华 南 师 范 大 学 实 验 报 告 学生姓名 学号 专业 计算机科学与技术 年级、班级 课程名称 并行计算 实验项目 快速排序的并行算法 实验类型验证设计综合实验时间 2011 年 6 月 10 日实验指导老师 实验评分 3
1 实验目的与要求 1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3
2 实验环境及软件 单台或联网的多台PC 机，Linux 操作系统，MPI 系统
3 实验内容 1、快速排序的基本思想 2、单处理机上快速排序算法 3、快速排序算法的性能 4、快速排序算法并行化 5、描述了使用2m 个处理器完成对n 个输入数据排序的并行算法
6、在最优的情况下并行算法形成一个高度为logn 的排序树 7、完成快速排序的并行实现的流程图 8、完成快速排序的并行算法的实现 3
4 实验步骤 3
1、 快速排序（Quick Sort）是一种最基本的排序算法，它的基本思想是：在当前无序区R[1，n]中取一个记录作为比较的“基准”（一般取第一个、最后一个或中间位置的元素），用此基准将当前的无序区R[1， n]划分成左右两个无序的子区R[1， i-1]和 R[i， n](1≤ i≤ n)，且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字；当R[1， i-1]和R[i， n]非空时，分别对它们重复上述的划分过程，直到所有的无序子区中的记录均排好序为止
2、 单处理机上快速排序算法 输入：无序数组data[1,n] 输出：有序数组data[1,n] Begin call procedu re qu icksort(data,1,n) End procedu re qu icksort(data,i,j) Begin
