procedure partition(data, k, 7) Begin (3)for j=k to l-1 do if data[l]≤ pivo then =1+1 exchange data[i] and data[jl end if (4) exchange data[i+ 1] and data(/ (5)return i+l 快速排序算法的性能主要决定于输入数组的划分是否均衡,而这与基准元素的选择密切 相关。在最坏的情况下,划分的结果是一边有n-1个元素,而另一边有0个元素(除去被选 中的基准元素)。如果每次递归排序中的划分都产生这种极度的不平衡,那么整个算法的复 杂度将是e(n2)。在最好的情况下,每次划分都使得输入数组平均分为两半,那么算法的 复杂度为O( nlogn)。在一般的情况下该算法仍能保持O( nlogn)的复杂度,只不过其具有 更高的常数因子。 122快速排序的并行算法 快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两 个处理器完成递归排序。例如对一个长为n的序列,首先划分得到两个长为n2的序列,将 其交给两个处理器分别处理;而后进一步划分得到四个长为n4的序列,再分别交给四个处 理器处理;如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况,如果划 分步骤不能达到平均分配的目的,那么排序的效率会相对较差。算法13.4中描述了使用2m 个处理器完成对n个输入数据排序的并行算法 算法13.4快速排序并行算法 输入:无序数组data[1n],使用的处理器个数2m 输出:有序数组data[1n Begin para quicksort(data, 1, n, m, O) End procedure para quicksort(data, i, j, m, id) Begin l)if(-i)≤korm=0 (1. 1)Pid call quicksort( data, i, j) (1.2)Pud:P→p (1.3)Pid send data[r+1, m-1]to Pid+ m- (1. 4)para quicksort( data, i, r -1, m-1, id) (1.5)para quicksort(data, r+1, j, m-1, id-+2m-)3 procedure partition(data,k,l) Begin (1) pivo=data[l] (2) i=k-1 (3) for j=k to l-1 do if data[j]≤pivo then i=i+1 exchange data[i] and data[j] end if end for (4) exchange data[i+1] and data[l] (5) return i+1 End 快速排序算法的性能主要决定于输入数组的划分是否均衡，而这与基准元素的选择密切 相关。在最坏的情况下，划分的结果是一边有 n-1 个元素，而另一边有 0 个元素（除去被选 中的基准元素）。如果每次递归排序中的划分都产生这种极度的不平衡，那么整个算法的复 杂度将是Θ（n 2）。在最好的情况下，每次划分都使得输入数组平均分为两半，那么算法的 复杂度为 O（nlogn）。在一般的情况下该算法仍能保持 O（nlogn）的复杂度，只不过其具有 更高的常数因子。 1.2.2 快速排序的并行算法 快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两 个处理器完成递归排序。例如对一个长为 n 的序列，首先划分得到两个长为 n/2 的序列，将 其交给两个处理器分别处理；而后进一步划分得到四个长为 n/4 的序列，再分别交给四个处 理器处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划 分步骤不能达到平均分配的目的，那么排序的效率会相对较差。算法 13.4 中描述了使用 2 m 个处理器完成对 n 个输入数据排序的并行算法。 算法 13.4 快速排序并行算法 输入：无序数组 data[1,n]，使用的处理器个数 2 m 输出：有序数组 data[1,n] Begin para_quicksort(data,1,n,m,0) End procedure para_quicksort(data,i,j,m,id) Begin (1) if (j-i)≤k or m=0 then (1.1)Pid call quicksort(data,i,j) else (1.2)Pid: r=patrition(data,i,j) (1.3)P id send data[r+1,m-1] to Pid+2m-1 (1.4)para_quicksort(data,i,r-1,m-1,id) (1.5)para_quicksort(data,r+1,j,m-1,id+2m-1 )