排序算法之：样本排序（Sample Sort）

题目描述
样本排序是一种并行排序算法，常用于分布式或内存受限的大规模数据排序。它的核心思想是：

1. 从待排序数组中随机选取一组“样本”（pivots），将数据划分为多个桶；
2. 将每个元素根据样本值分配到对应的桶中；
3. 对每个桶独立排序（通常用快速排序等），最后合并结果。
   题目要求：实现样本排序的串行版本，并解释其如何扩展为并行算法。

解题过程

步骤1：理解样本排序的流程
样本排序可看作快速排序的推广，但通过预先选取多个枢轴（pivots）来更均匀地划分数据，避免快速排序在不平衡划分时的性能退化。流程如下：

1. 采样阶段：从原数组中随机选取 \(k \times p\) 个样本（\(p\) 为桶的数量，\(k\) 为采样系数，通常 \(k \geq 2\)）。
2. 排序样本：对样本进行排序，选出 \(p-1\) 个分界点（如均匀选取样本中的第 \(k, 2k, \dots, (p-1)k\) 位置的元素作为枢轴）。
3. 分配阶段：遍历数组，根据枢轴将元素分到 \(p\) 个桶中。
4. 排序桶：对每个桶调用排序算法。
5. 合并结果：按桶顺序连接排序后的结果。

步骤2：实现串行样本排序
以 \(p=3\) 为例，详细步骤如下：

1. 采样

   • 假设数组为 arr，长度为 n。
   • 随机选取 \(3 \times 2 = 6\) 个样本（例如通过随机索引）。
   • 对样本排序，取第 2、第 4 个样本作为两个枢轴 pivot1、pivot2（将数据分为 3 个桶：小于 pivot1、介于 pivot1 和 pivot2 之间、大于 pivot2）。

2. 分配元素到桶

   • 创建三个空桶 bucket1、bucket2、bucket3。
   • 遍历 arr：
     • 若 arr[i] < pivot1，放入 bucket1；
     • 若 pivot1 ≤ arr[i] < pivot2，放入 bucket2；
     • 否则放入 bucket3。

3. 排序每个桶

   • 对 bucket1、bucket2、bucket3 分别调用快速排序（或其它排序算法）。

4. 合并

   • 按顺序连接 bucket1、bucket2、bucket3。

示例代码（Python）

import random

def sample_sort(arr, p=3, k=2):
    n = len(arr)
    if n <= 1:
        return arr
    
    # 1. 采样
    samples = random.sample(arr, min(k * p, n))
    samples.sort()
    
    # 2. 选择枢轴
    step = len(samples) // p
    pivots = [samples[step * i] for i in range(1, p)]
    
    # 3. 分桶
    buckets = [[] for _ in range(p)]
    for num in arr:
        idx = 0
        while idx < len(pivots) and num >= pivots[idx]:
            idx += 1
        buckets[idx].append(num)
    
    # 4. 排序每个桶并合并
    result = []
    for bucket in buckets:
        result.extend(sorted(bucket))  # 可用任意排序算法
    return result

步骤3：分析并行化思路
样本排序的并行版本通常按以下步骤设计：

1. 全局采样：每个处理器从本地数据中抽取样本，汇总后全局排序，选出枢轴。
2. 数据划分：所有处理器根据全局枢轴将本地数据分到对应桶中。
3. 桶交换：每个桶的数据被发送到对应的目标处理器（如桶 \(i\) 由处理器 \(i\) 负责）。
4. 局部排序：每个处理器对接收到的桶内数据排序。
5. 结果收集：按处理器顺序输出结果。

关键点：通过样本保证桶的大小均衡，避免并行时负载不均。

步骤4：复杂度与适用场景

• 串行样本排序的平均时间复杂度为 \(O(n \log n)\)，与快速排序相同，但通过样本划分减少了最坏情况概率。
• 并行版本适用于分布式系统（如 MPI 或 MapReduce），能高效处理海量数据。

总结
样本排序通过多枢轴划分提升数据分布的均匀性，串行版本易于实现，并行版本可扩展性强，是大规模排序的重要算法之一。