1. 简介
双调排序是一种基于比较的排序算法，和奇偶排序（Odd-Even Transposition Sort）类似，但其最大优势在于易于并行化。在处理大规模数据时，双调排序在并行环境下表现优异。
2. 问题描述
我们希望将一个无序数组排序为非降序排列。例如：
- 输入：
[200, 20, 191, 345, 10001] - 输出：
[20, 191, 200, 345, 10001]
注意：双调排序要求输入数组的长度为2的幂次。如果不是，我们可以通过补足比原数组最大值更大的元素来扩展数组长度，排序后再截取前n个即可。
3. 双调排序原理
3.1. 双调序列（Bitonic Sequence）
一个序列是双调的，当它满足以下任意一个条件：
✅ 序列先递增后递减
✅ 通过循环移位后满足上述条件
例如：[1, 11, 23, 45, 36, 31, 20, 8] 是一个双调序列，因为45之后开始递减。
⚠️ 注意：双调排序的输入数组长度必须是2的幂次，否则需要补足。
3.2. 核心思想
双调排序分为两个主要阶段：
- 构建双调序列：递归地将输入数组构造成一个双调序列
- 合并双调序列：将双调序列的两个单调部分合并成一个有序数组
流程图如下：
3.3. 伪代码实现
algorithm BitonicSort(arr, direction):
// arr: 待排序数组
// direction: 排序方向，"ascending" 或 "descending"
n = arr.length
if n > 1:
BitonicSort(arr[1 : n/2], "ascending")
BitonicSort(arr[n/2 + 1 : n], "descending")
Merge(arr, direction)
function Merge(arr, direction):
n = arr.length
if n > 1:
for i from 1 to n/2:
if (direction == "ascending" and arr[i] > arr[i + n/2]) or
(direction == "descending" and arr[i] < arr[i + n/2]):
swap arr[i] and arr[i + n/2]
Merge(arr[1 : n/2], direction)
Merge(arr[n/2 + 1 : n], direction)
4. 示例说明
4.1. 构建双调序列
以输入数组 [19, 2, 72, 3, 18, 57, 603, 101] 为例，逐步构建出双调序列的过程如下：
在这个过程中，我们使用 min() 和 max() 比较器来构建递增和递减子序列，最终形成两个单调方向相反的子序列。
4.2. 从双调序列到有序数组
完成构建后，进入排序阶段。通过递归地进行比较和交换操作，最终得到一个有序数组：
在这个阶段中，我们不断缩小比较器跨度，最终将整个数组排序。
5. 时间复杂度分析
- 每层递归包含
n/2次比较 - 递归深度为
log₂n - 总比较次数为：
n/2 × log₂n
因此，双调排序的时间复杂度为：O(n (log n)²)
6. 并行化潜力
双调排序本质上是顺序算法，但在并行环境下效率显著提升。其优势在于：
✅ 比较操作顺序固定，不依赖输入数据
✅ 便于负载均衡
✅ 适合多核处理器或网格化硬件系统
当使用 p 个处理器时，排序 n 个元素的时间复杂度为：θ((n/p) (log n)²)
7. 优缺点分析
| 优点 | 缺点 |
|---|---|
| ✅ 并行性能优异 | ❌ 比较次数多于快速排序等算法 |
| ✅ 不依赖输入数据动态调整 | ❌ 要求数组长度为2的幂次 |
| ✅ 适合硬件并行实现 | ❌ 顺序执行效率不高 |
8. 总结
双调排序是一种适合并行处理的排序算法。其核心在于：
- 递归构建双调序列
- 再通过固定模式的比较操作将其排序
虽然在顺序执行中不如快速排序高效，但在并行系统中，其性能优势明显。特别适合用于GPU计算、多核处理器等场景。