求可替代std::shuffle与Fisher-Yates的小众随机洗牌算法实现方案

以下几个算法不需要依赖std::shuffle或Fisher-Yates，且实现简单，适合你的作业需求：

1. 多次随机交换法 #

这个算法的核心思路是通过大量随机交换数组中的元素对来实现打乱效果。虽然时间复杂度较高（通常需要O(k*n)次操作，k是一个足够大的常数，比如n或n²），但实现非常直观，只要交换次数足够，就能得到效果不错的洗牌结果。

实现示例（C++） #

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

void shuffleByRandomSwaps(std::vector<int>& arr) {
    srand(time(nullptr));
    int n = arr.size();
    // 执行n*n次随机交换，确保打乱充分
    for (int i = 0; i < n * n; ++i) {
        int idx1 = rand() % n;
        int idx2 = rand() % n;
        std::swap(arr[idx1], arr[idx2]);
    }
}

int main() {
    std::vector<int> nums = {1,2,3,4,5,6};
    shuffleByRandomSwaps(nums);
    for (int num : nums) {
        std::cout << num << " ";
    }
    return 0;
}

2. 随机优先级排序法 #

给数组中的每个元素分配一个随机生成的优先级值，然后按照这个优先级对数组进行排序。排序完成后，原数组的顺序就会被随机打乱。这个方法的复杂度由排序算法决定（通常O(n logn)），但实现简单，且打乱效果均匀。

实现示例（C++） #

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

void shuffleByPrioritySort(std::vector<int>& arr) {
    srand(time(nullptr));
    int n = arr.size();
    // 存储元素和对应的随机优先级
    std::vector<std::pair<int, int>> temp;
    for (int num : arr) {
        temp.emplace_back(num, rand());
    }
    // 按随机优先级排序
    std::sort(temp.begin(), temp.end(), [](const auto& a, const auto& b) {
        return a.second < b.second;
    });
    // 将排序后的元素放回原数组
    for (int i = 0; i < n; ++i) {
        arr[i] = temp[i].first;
    }
}

int main() {
    std::vector<int> nums = {1,2,3,4,5,6};
    shuffleByPrioritySort(nums);
    for (int num : nums) {
        std::cout << num << " ";
    }
    return 0;
}

3. 随机插入法 #

遍历原数组的每个元素，将当前元素随机插入到结果数组的任意位置（包括开头、中间或末尾）。每次插入操作都会改变结果数组的结构，最终得到一个打乱的数组。这个方法的时间复杂度是O(n²)（因为插入元素到中间位置需要移动元素），但逻辑简单易懂。

实现示例（C++） #

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

void shuffleByRandomInsertion(std::vector<int>& arr) {
    srand(time(nullptr));
    std::vector<int> shuffled;
    for (int num : arr) {
        // 生成0到当前shuffled数组长度的随机索引（可以插入到末尾）
        int insertPos = rand() % (shuffled.size() + 1);
        shuffled.insert(shuffled.begin() + insertPos, num);
    }
    arr.swap(shuffled);
}

int main() {
    std::vector<int> nums = {1,2,3,4,5,6};
    shuffleByRandomInsertion(nums);
    for (int num : nums) {
        std::cout << num << " ";
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Hannah