华 南 师 范 大 学 实 验 报 告 学生姓名 学号 专业 计算机科学与技术 年级、班级 课程名称 并行计算 实验项目 快速排序的并行算法 实验类型验证设计综合实验时间 2011 年 6 月 10 日实验指导老师 实验评分 3.1 实验目的与要求 1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC 机，Linux 操作系统，MPI 系统。 3.3 实验内容 1、快速排序的基本思想 2、单处理机上快速排序算法 3、快速排序算法的性能 4、快速排序算法并行化 5、描述了使用2m 个处理器完成对n 个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn 的排序树 7、完成快速排序的并行实现的流程图 8、完成快速排序的并行算法的实现 3.4 实验步骤 3.4.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]非空时，分别对它们重复上述的划分过程，直到所有的无序子区中的记录均排好序为止。 3.4.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 (1) if (i
