查看“︁并行排序”︁的源代码

{{NoteTA|G1=IT|1=zh-hans:并行;zh-hant:平行}}
{{Unreferenced|time=2020-04-29T03:26:22+00:00}}
'''并行排序'''算法是计算机并行计算能力大大发展之后，为了提高排序效率而提出的算法。

==划分的设计方法==
*[[PSRS算法]]
*[[Viliant归并算法]]
*对数划分

==串行算法直接并行化==
*模拟快速排序
**'''二叉树上模拟快速排序'''
***串行算法简介：[[快速排序]]是一种较为高效的排序算法，它通过不断的划分待排序列为两段，使得前一段总小于或等于某个数，而后一段总大于某个数，这样每次划分就能确定一个数的最终位置。一般情况下，如果每次划分的两个子列大致等长，那么它的时间复杂度是<math>O \left ( n \log n \right )</math>。
***在[[PRAM-CRCW]]计算模型上利用二叉树网络模拟快速排序
**** 由快速排序的过程，我们可以看到，快速排序实际上就是在构造一棵[[二叉树]]，让划分主元位于根节点，使得左子节点小于或等于根而右子节点大于根，最后对整棵二叉树进行一次[[中序遍历]]，便可以得到最后排好序的数列。
**** 我们可以选n个处理器分别保存待排序数组A的n个元素，处理器<math>P_i</math>对应一个变量<math>X_i</math>用于存放主元元素的处理器号，以及两个变量L,R分别存放其左右儿子。开始时，每一个处理器都试图往变量root中写入它的处理器号，若果我们使用[[PRAM-CRCW]]计算模型，那么就只有一个能够写入root，接着root被复制给每一个处理器的<math>X_i</math>。然后对于每个处理器（除去被原为主元的那个外）判断其值与<math>A_{X_i}</math>的大小，从而确定放入<math>L_{X_i}</math>还是<math>R_{X_i}</math>，同样的，由于并发操作的互斥性，只有一个只能被最终写入，他们就作为下次划分的主元。算法继续进行直到n个主元被选完为止。
***时间复杂度分析：由于一层节点的构造时间是<math>\Theta (1)</math>，所以算法的时间复杂度是<math>\Theta (logn)</math>
**'''超立方体上模拟快速排序'''
***超立方体网络是基于[[超立方体连接]]构建的网络。网络中以[[格雷码]]对各顶点编号。在下面的描述中，设顶点数<math>p=2^d</math>，待排序元素共有n个。
*** 超立方体上的快速排序是这样进行的：首先我们将n个元素分配到p个处理器上，为了使问题讨论简单化，假设n是p的整数倍，那么每个顶点将会分到<math>\frac{n}{p}</math>个元素。然后随机选一个主元，各个处理器将每个顶点中的元素按与主元的比较结果分为两部份。这个算法的关键点在这里，对每一个处理器（顶点）在进行第i次划分时，将大于主元的部分都送到超立方体的一个d-i维自立方体中，而将小于主元的部分送到另一个d-i位的子立方体中，这样就模拟了快速排序中的划分算法。子立方体可以这样选择：在第i次划分中判断第i位是0还是1。划分算法到处理完所有1维子立方体后结束。接下来对每个顶点中的元素调用串行算法进行局部排序，最后对整个立方体进行一次遍历便可得到排好序的元素。

==比较器络上的并行排序网==
{{link-en|排序网络|sorting network|比较器网络}}一般是指由'''Batcher比较器'''构成的网络。这些比较器均可以执行两个数之间的比较与条件交换(CCI)操作。[[Batcher归并网络]]可以由较小的Batcher归并网络[[递归]]地组成。Batcher排序网络可以分为[[Batcher归并网络#奇偶归并网络|奇偶排序网络(Odd-Even Sorting Network)]]和{{link-en|双调排序网络|Bitonic Sorting Net}}两大类。

==参阅==
*[[并行计算]]
*[[高德纳]]的[[0-1原理]]
{{排序算法表}}
{{算法}}

[[Category:并发计算]]
[[Category:排序算法]]
[[Category:算法]]