输入:无序数组a[]…an] 输出:有序数组b[]…bn Begin 1)P播送a[]…an给所有 (2) for all Pi where I≤i≤ n para-do (2.1)k=1 (2.2)forj=I to n do if(a[i]>aDor(a0=a[] and i>j then k=k+1 end if end for (3)P收集k并按序定位 在该并行算法中,使用了n个处理器,由于每个处理器定位一个元素,所以步骤(2)的时 间复杂度为O(n):步骤(3)中主进程完成的数组元素重定位操作的时间复杂度为O(n),通 信复杂度分别为O(n):同时(1)中的通信复杂度为O(n2):所以总的计算复杂度为O(n) 总的通信复杂度为O(n2)。 MPI源程序请参见所附光盘。 12快速排序 121快速排序及其串行算法 快速排序( 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非空时,分别对它们重 复上述的划分过程,直到所有的无序子区中的记录均排好序为止。 算法13.3单处理机上快速排序算法 输入:无序数组data[1n 输出:有序数组data1n call procedure quicksort( data, I, n) procedure quicksort(data, i,j) Begin (1)ifi<))then (1. I)r= partition( data, i,j) (1.2)quicksort(data, i, r-1) (1.3)quicksort(data, r+1, j) end if End2 输入：无序数组 a[1]…a[n] 输出：有序数组 b[1]…b[n] Begin (1) P0 播送 a[1]…a[n]给所有 Pi (2) for all Pi where 1≤i≤n para-do (2.1)k=1 (2.2)for j = 1 to n do if (a[i] > a[j]) or (a[i] = a[j] and i>j) then k = k+1 end if end for (3) P0 收集 k 并按序定位 End 在该并行算法中，使用了 n 个处理器，由于每个处理器定位一个元素，所以步骤⑵的时 间复杂度为 O（n）；步骤⑶中主进程完成的数组元素重定位操作的时间复杂度为 O（n），通 信复杂度分别为 O（n）；同时⑴中的通信复杂度为 O（n 2）；所以总的计算复杂度为 O（n）， 总的通信复杂度为 O（n 2）。 MPI 源程序请参见所附光盘。 1.2 快速排序 1.2.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]非空时，分别对它们重 复上述的划分过程，直到所有的无序子区中的记录均排好序为止。 算法 13.3 单处理机上快速排序算法 输入：无序数组 data[1,n] 输出：有序数组 data[1,n] Begin call procedure quicksort(data,1,n) End procedure quicksort(data,i,j) Begin (1) if (i<j) then (1.1)r = partition(data,i,j) (1.2)quicksort(data,i,r-1); (1.3)quicksort(data,r+1,j); end if End