平均情况下桶排序以线性时间运行。像计数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。具体来说，计数排序假设输入是由一个小范围内的整数构成，而桶排序则 假设输入由一个随机过程产生，该过程将元素一致地分布在区间［0，1）上。 桶排序的思想就是把区间［0，1）划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在［0，1）上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。 在桶排序算法的代码中，假设输入是个含n个元素的数组A，且每个元素满足0≤ A[i]<1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶，并假设可以用某种机制来维护这些表。桶排序的算法如下，其中 floor(x)是地板函数，表示不超过x的最大整数。 |
为了在PRAM中存储二叉树，我们采用了简单的二叉树表示法。每个结点i有三个域 parent[i],left[i],right[i]，分别指向结点i的父母、左子女和右子女。假定每个结点用一个非负整数来表示。我们为每个结点联接 三个而不是一个处理器，其原因我们在下面将会明白。称这三个处理器为结点的A，B和C处理器，我们可以很容易地在结点与其三个处理器之司找出对应关系。例 如，结点i可以与处理器3i，3i+1和3i+2相联接。 在串行RAM上，计算包含n个结点的树中每个结点的深度所需运行时间为O(n)。采用一种简单的并行算法来计算结点深度时，算法可以从树的根结点开始把一种“波”向下传输。这种波同时到达深度相同的所有结点，因此通过对波载计数器增值，我们就能计算出每个结点的深度。 这种并行算法对完全二叉树很适用，这是因为其运行时间与树的高度成正此。而树的高度最大为n-1，这时算法的运行时间为O(n)，这并不优于串行算法。 但是，如果我们运用欧拉回路技术，不论树的高度是多少，都能够在EREW PRAM上用O(lgn)的运行时间计算出结点的深度。 一 个图的欧拉回路是通过图的每条边一次一个回路，当然，在此过程中它可以多次访问一个结点。根据图论算法可知，一个有向连通图具有欧拉回路当且仅当对所有结 点v，v的出度等于v的入度。因为无向图每条无向边(u，v)对应于相应的有向图中的两条边(u，v)和(v，u)，因此任何无向连通图改成的有向图均包 含欧拉回路，这对无向树也自然成立。  （a）  （b） 图4 运用欧拉回路技术来计算每个结点在二叉树中的深度 1. 如果结点的左子女存在，则结点的A处理器指向其左子女的A处理器，否则就指向自身的B处理器； 2. 如果结点存在右子女，则结点的B处理器指向其右子女的A处理器，否则就指向其自身的C处理器。 3. 如果一个结点是其父母结点的左子女，则结点的C处理器指向其父母的B处理器，如果该结点是其父母结点的右子女，则结点的C处理器指向其父母的C处理器。根结点的C处理器指向NIL。 因此，根据欧拉回路形成的链表的表头是根结点的A处理器，表尾是根节点的C处理器。如果已知构成原始树的指针，则我们可以在O(1)的时间内构造出欧拉回路。 在我们获得表示T的欧拉回路的链表后，我们在每个A处理器中放入值1，在每个B处理器中放入值0，在每个C处理器中放入值-1，如图4(a)所示。然后如第1.2节中那样，我们运用满足结合律的普通加法来执行并行前缀计算。图4(b)说明了并行前缀计算的结果。 我们说，在执行完并行前缀计算过程后，每个结点的深度值在结点的C处理器中。为什么呢？我们按以下要求把数放入A，B和C三个处理器中：访问子树的最后 结果是把运行和加上0。每个结点i的A处理器对其左子女树的运行和加1，这表明i的左子女的深度比i的深度大1。B处理器对运行和没有影响，这是因为i的 左子女的深度与其右子女的深度相等。C处理器使运行和减1，以便对i的父母结点来说，对以i为根结点的子树进行访问后运行和不会改变。 我们可以在O(1)的时间内计算出表示欧拉回路的列表。列表中包含3n个对象，所以执行并行前缀计算过程仅需O(lgn)的运行时间。因此，计算所有结 点深度所花费的全部运行时间为O(lgn)。又因为算法执行中不需要对有存储器执行并发存取操作，所以该算法是一个EREW算法。 |
