双调排序（Bitonic Sort）

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. 核心思想

双调排序分为两个主要阶段：

1. 构建双调序列：递归地将输入数组构造成一个双调序列
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计算、多核处理器等场景。