随机抽奖算法实现与对比：聚焦洗牌算法（Fisher-Yates）-洪萨配资

期末课程设计中，我和团队成员共同完成了 “随机抽奖算法实现与比较” 的课题。本次设计的核心目标是模拟实际抽奖场景，从指定号码范围（min_num 到 max_num）中抽取 k 个不重复的中奖号码，并通过实现四种不同算法，对比其效率、公平性与适用场景，为实际应用提供参考。其中，我主要负责洗牌算法（Fisher-Yates 版本）的设计与实现，这也是本次设计中公平性和效率兼具的核心算法之一。。

一、课题背景与核心要求

1. 场景描述

模拟实际抽奖活动，需从连续整数区间 [min_num, max_num] 中抽取 k 个不重复号码，核心是保证算法的合理性（无重复）、高效性（低时间 / 空间开销），同时兼顾不同场景的需求（如公平抽奖、偏向性抽奖等）。

2. 设计目标

实现四种随机抽奖算法，对比其时间复杂度、空间复杂度、优缺点及适用场景，最终形成可落地的技术方案。四种算法分别为：基础随机法、洗牌算法、加权随机法、批量随机法。

二、四种算法简要概述

在深入讲解洗牌算法前，先快速梳理另外三种算法的核心逻辑，方便对比理解：

算法名称	核心思路	关键特点
基础随机法	逐个生成随机数，暴力遍历查重，重复则重生成	逻辑最简单，但 k 接近总数时重复率高，效率 O (k²)
加权随机法	为每个号码分配权重，按累积权重区间随机选择	可实现偏向性抽奖（如新员工高概率中奖），时间复杂度 O (kn)
批量随机法	一次生成 2k 个随机数，用哈希表批量去重	平衡时间与空间，平均时间复杂度 O (k)，通用场景优选
洗牌算法	模拟洗牌发牌，先打乱全量号码池，再取前 k 个	绝对公平、无重复，时间复杂度 O (n)，效率高

三、洗牌算法（Fisher-Yates）详解

1. 算法核心思想

洗牌算法的灵感源于 “洗扑克牌 + 发牌”：先将所有可选号码（[min_num, max_num]）按顺序排成 “一摞牌”（号码池），然后通过随机交换位置的方式彻底打乱这摞牌，最后直接从打乱后的牌堆中取前 k 个号码，即为中奖结果。

核心优势：每个号码被选中的概率完全相等（绝对公平），且天然无重复，无需额外查重步骤。

2. 算法原理与流程

（1）核心原理

Fisher-Yates 洗牌算法的关键是 “从后往前遍历 + 随机交换”：

遍历号码池时，从最后一个元素开始，每次为当前位置随机选择一个 “未被打乱的位置”（即索引范围 [0, 当前位置]）；
将当前位置的元素与随机位置的元素交换，确保每个元素被放到任意位置的概率均等；
遍历结束后，号码池完全打乱，取前 k 个元素即可（也可取后 k 个，本质一致）。

（2）完整流程

参数合法性校验：判断 min_num > max_num、k ≤ 0 等非法情况，若非法直接返回空结果；
构建号码池：将 [min_num, max_num] 区间内的所有整数存入向量（vector），模拟 “一整副牌”；
容错处理：若 k ≥ 号码池总数（即要抽的数量≥可选数量），直接返回全部号码（全中）；
核心洗牌：从号码池末尾（索引 n-1）向前遍历至索引 n-k，每次生成 [0, 当前索引] 的随机数，交换当前位置与随机位置的元素；
结果截取：截取打乱后号码池的最后 k 个元素（或前 k 个），作为中奖结果返回。

3. 代码实现（C++）

cpp

运行

#include <vector> #include <cstdlib> #include <algorithm> // for swap using namespace std; vector<int> randomDraw_shuffle(int min_num, int max_num, int k) { vector<int> pool; // 1. 参数合法性校验 if (min_num > max_num || k <= 0) { return pool; } // 2. 构建完整号码池（[min_num, max_num]） for (int i = min_num; i <= max_num; ++i) { pool.push_back(i); } int n = pool.size(); // 3. 容错处理：k≥总数则返回全部 if (k >= n) { return pool; } // 4. Fisher-Yates 核心洗牌逻辑（从后往前交换） for (int i = n - 1; i >= n - k; --i) { // 生成 [0, i] 范围内的随机索引 int rand_idx = rand() % (i + 1); // 交换当前位置与随机位置的元素 swap(pool[i], pool[rand_idx]); } // 5. 截取最后 k 个元素作为结果 vector<int> result(pool.end() - k, pool.end()); return result; }

4. 复杂度分析

时间复杂度：O(n)构建号码池需遍历 n 个元素（O (n)），洗牌过程遍历 n 次（O (n)），截取结果为 O (k)（k ≤ n），总复杂度为线性阶 O (n)，效率极高。
空间复杂度：O(n)需要存储完整的号码池，空间消耗与号码总数 n 成正比，适合号码范围不大的场景（如 1-1000 抽奖）。

5. 关键优化与注意事项

随机数种子：需在主函数中调用srand(time(nullptr))，确保每次运行程序的洗牌结果不同（避免固定中奖号码）；
公平性保障：“从后往前遍历 + 随机索引范围 [0, i]” 是 Fisher-Yates 算法的核心，若索引范围错误（如 [0, n-1]），会导致概率不均；
边界处理：当 k=0 或 k 超过号码池总数时，直接返回空或全量号码，避免数组越界错误。

四、四种算法性能对比

为了更清晰地体现洗牌算法的优势，整理了四种算法的核心指标对比：

算法名称	时间复杂度	空间复杂度	优点	缺点	适用场景
基础随机法	O(k²)	O(k)	逻辑简单、易实现	效率低，k 接近 n 时性能骤降	小规模抽奖（如 k≤10，n≤50）
洗牌算法	O(n)	O(n)	绝对公平、无重复、速度快	内存占用与 n 成正比	号码范围不大（n≤10000）、追求公平的场景
加权随机法	O(kn)	O(n+k)	可自定义中奖概率	实现复杂，效率中等	偏向性抽奖（如年会老员工 / 新员工倾斜）
批量随机法	平均 O (k)	O(k)	时间空间平衡、通用高效	需调整批量大小参数	大规模抽奖、对内存敏感的场景