13. 随机化算法

习题

#31301

⚡3⏳3

实现 Fisher–Yates 洗牌：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef uint64_t (*RandomBits)(void *context);

bool shuffle_i64(
    int64_t *items,
    size_t count,
    RandomBits random_bits,
    void *context
);

要求：

1. 原地生成所有排列的等概率分布；count <= 1 时不要求随机源非空。
2. 不得直接用随机数对上界取余而引入模偏差，应使用拒绝采样或等价方法。
3. 参数无效时返回 false；时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

#31302

⚡4⏳3

实现随机选择第 order 小的元素：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef uint64_t (*RandomBits)(void *context);

bool randomized_select_i64(
    int64_t *items,
    size_t count,
    size_t order,
    RandomBits random_bits,
    void *context,
    int64_t *out_value
);

要求：

1. order 从 0 开始计数；数组允许被原地重排，重复元素必须正确处理。
2. 使用随机枢轴和三路分区，平均时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$（不计递归栈）。
3. 参数无效时不得修改数组和输出对象；随机下标选择不得产生模偏差。

#31303

⚡4⏳3

实现随机化快速排序：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef uint64_t (*RandomBits)(void *context);

bool randomized_quicksort_i64(
    int64_t *items,
    size_t count,
    RandomBits random_bits,
    void *context
);

要求：

1. 使用随机枢轴和三路分区，支持重复元素和 int64_t 的全部取值。
2. 原地排序为非递减顺序；参数无效时不得修改数组。
3. 平均时间复杂度为 $O(n\log n)$；优先递归较小分区、循环处理较大分区，使额外调用栈空间保持为 $O(\log n)$。
4. 说明随机化如何降低固定输入导致的最坏分区风险，但不能把平均复杂度当成最坏保证。