l排序 排序是数据处理中经常使用的一种重要运算,如何进行排序,特别是如何进行高效的排 序,是计算机应用中的重要课题。排序的对象一般是一组记录组成的文件,而记录则是由若 干数据项组成,其中的一项可用来标志一个记录,称为关键字项,该数据项的值称为关键字。 所谓排序,就是要整理文件中的记录,使得它按关键字递增(或递减)的次序排列起来。若 给定的文件含有n个记录{R,R Rn},它们的关键字分别为{K 要把这n个记录重新排列成为{R1,R12,…,Rn},使得{K1≥Ka≥…≥Kn}(或{K1≤ K2≤…≤Kin})。 本章主要介绍了枚举排序、快速排序、PSRS排序算法以及它们的MPI编程实现。 11枚举排序 111枚举排序及其串行算法 枚举排序( Enumeration sort)是一种最简单的排序算法,通常也称为秩排序( Rank sort)。 该算法的具体思想是(假设按关键字递增排序),对每一个待排序的元素统计小于它的所有 元素的个数,从而得到该元素最终处于序列中的位置。假定待排序的n个数存在a[1]…an 中。首先将a[1与a[2]…an比较,记录比其小的数的个数,令其为k,a[]就被存入有序的 数组b[]…b[m的b[k+]位置上:然后将a[2]与a(1],a[3…am比较,记录比其小的数的个 数,依此类推。这样的比较操作共n(n-1)次,所以串行秩排序的时间复杂度为O(n2)。 算法13.1枚举排序串行算法 输入:a[]…an 输出:b[l…bn Be for i=l to n do (2)for j= ifa[i≥a[ 1 then end for (3)b[k}=a[ end for End 112枚举排序的并行算法 对该算法的并行化是很简单的,假设对一个长为n的输入序列使用n个处理器进行排序, 只需是每个处理器负责完成对其中一个元素的定位,然后将所有的定位信息集中到主进程 中,由主进程负责完成所有元素的最终排位。该并行算法描述如下 算法13.2枚举排序并行算法1 1. 1 排序 排序是数据处理中经常使用的一种重要运算，如何进行排序，特别是如何进行高效的排 序，是计算机应用中的重要课题。排序的对象一般是一组记录组成的文件，而记录则是由若 干数据项组成，其中的一项可用来标志一个记录，称为关键字项，该数据项的值称为关键字。 所谓排序，就是要整理文件中的记录，使得它按关键字递增（或递减）的次序排列起来。若 给定的文件含有 n 个记录｛R1，R2，…，Rn｝，它们的关键字分别为｛K1，K2，…，Kn｝， 要把这 n 个记录重新排列成为｛Ri1，Ri2，…，Rin｝，使得｛Ki1≥Ki2≥…≥Kin｝（或｛Ki1≤ Ki2≤…≤Kin｝）。 本章主要介绍了枚举排序、快速排序、PSRS 排序算法以及它们的 MPI 编程实现。 1.1 枚举排序 1.1.1 枚举排序及其串行算法 枚举排序（Enumeration Sort）是一种最简单的排序算法，通常也称为秩排序（Rank Sort）。 该算法的具体思想是（假设按关键字递增排序），对每一个待排序的元素统计小于它的所有 元素的个数，从而得到该元素最终处于序列中的位置。假定待排序的 n 个数存在 a[1]…a[n] 中。首先将 a[1]与 a[2]…a[n]比较，记录比其小的数的个数，令其为 k，a[1]就被存入有序的 数组 b[1]…b[n]的 b[k+1]位置上；然后将 a[2]与 a[1]，a[3]…a[n]比较，记录比其小的数的个 数，依此类推。这样的比较操作共 n(n-1)次，所以串行秩排序的时间复杂度为 O（n 2）。 算法 13.1 枚举排序串行算法 输入：a[1]…a[n] 输出：b[1]…b[n] Begin for i=1 to n do (1) k=1 (2) for j=1 to n do if a[i]>a[j] then k=k+1 end if end for (3) b[k]= a[i] end for End 1.1.2 枚举排序的并行算法 对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序， 只需是每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程 中，由主进程负责完成所有元素的最终排位。该并行算法描述如下： 算法 13.2 枚举排序并行算法