C语言：使用指针填充无重复整数数组的优化方案探讨

算力阿峰

2026-7-19

优化无重复随机整数数组填充的实现方案（指针版）

你的现有实现虽然能完成功能，但存在效率短板：当MAX_SIZE较大时，越到后期生成不重复随机数的概率越低，会频繁触发重复检查循环，整体时间复杂度为O(n²)，数组规模越大性能下降越明显。

更高效的方案是采用Fisher-Yates洗牌算法，它能在**O(n)**时间复杂度内生成无重复的随机排列，且完全可以用纯指针操作实现，符合作业要求。

优化后的代码实现

#include <stdlib.h>
#include <time.h>

// 假设MAX_SIZE为已定义的常量宏，例如#define MAX_SIZE 4

void fillingArray(int *arr) {
    // 第一步：用指针初始化数组为0到MAX_SIZE-1的有序序列
    int *current = arr;
    for (int val = 0; val < MAX_SIZE; ++val) {
        *current = val;
        current++;
    }

    // 第二步：Fisher-Yates洗牌，纯指针操作交换元素
    current = arr + MAX_SIZE - 1; // 指向数组最后一个元素
    while (current > arr) {
        // 计算当前元素与起始元素的偏移量，生成随机交换位置
        int offset = current - arr;
        int randomOffset = rand() % (offset + 1); // 生成0到offset范围内的随机数
        int *swapPtr = arr + randomOffset;

        // 交换两个指针指向的元素值
        int temp = *current;
        *current = *swapPtr;
        *swapPtr = temp;

        current--;
    }
}

// 注意：使用前需在程序入口处调用srand(time(NULL))初始化随机数种子，避免每次生成相同序列