C++ STL random_shuffle 算法詳解：打亂容器元素順序

random_shuffle 是 STL 中經典的隨機排列算法，可將任意隨機訪問迭代器範圍內的元素隨機重排。本文講解用法、實現原理、C++11/14/17 演進與替代方案。

1. 基本用法

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<std::string> days = {"Sunday", "Monday", "Tuesday", 
                                     "Wednesday", "Thursday", "Friday", "Saturday"};
    
    std::random_shuffle(days.begin(), days.end()); // 打亂順序
    
    for (const auto& d : days) std::cout << d << ' ';
    // 輸出示例：Thursday Sunday Wednesday Monday Saturday Tuesday Friday
}

2. 算法特性

• 通用性：適用於所有隨機訪問迭代器（vector、deque、array、指針）
• 原地操作：不分配額外內存，直接交換元素
• 均勻分佈：標準要求每種排列概率相等（取決於隨機數生成器質量）
• 時間複雜度：O(N)，N 為元素數量

3. 自定義隨機數生成器（C++11 前）

std::random_shuffle(v.begin(), v.end(), [](){ return std::rand() % N; }); // 非推薦
// 或
struct MyRand { int operator()(int n) { return std::rand() % n; } };
std::random_shuffle(v.begin(), v.end(), MyRand());

⚠️ std::rand() 質量差、非線程安全、取模偏差。

4. C++11/14/17 演進：棄用與替代

5. 現代標準寫法

#include <random>
#include <algorithm>

std::vector<int> v = {1,2,3,4,5,6,7};
std::mt19937 rng(std::random_device{}()); // 高質量隨機引擎
std::shuffle(v.begin(), v.end(), rng); // 唯一標準方式

優勢：均勻分佈、周期長、線程安全（引擎可局部）、標準合規。

6. 適用容器限制

• ✅ vector、deque、array、string、C 數組
• ❌ list、forward_list、set、map（非隨機訪問迭代器）

若需打亂 list，可轉 vector 打亂再轉回，或手動實現 Fisher-Yates。

總結

random_shuffle 是歷史產物，現代 C++ 請直接使用 std::shuffle + std::mt19937。理解 Fisher-Yates 洗牌算法原理（從後向前隨機交換）有助於面試與自定義實現。