寻找数组元素最小差值的更优算法及C语言实现与性能测试

1. 原始O(n²)算法（pair1） #

该算法通过双重遍历所有元素对，计算差值并记录最小值，时间复杂度为O(n²)，适用于小规模数组。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 原始O(n²)复杂度算法
int pair1(int A[], int n) {
    if (n < 2) return -1; // 处理元素不足的边界情况
    int dmin = INT_MAX;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int diff = abs(A[i] - A[j]);
            if (diff < dmin) {
                dmin = diff;
            }
        }
    }
    return dmin;
}

2. 优化O(nlogn)排序算法（修正后的pair2） #

排序后，数组的最小差值必然出现在相邻元素之间，因此只需遍历一次排序后的数组即可找到结果，整体时间复杂度由排序的O(nlogn)主导。

伪代码 #

Function pair2(A, n):
    if n < 2:
        return -1
    复制原数组避免修改输入
    将复制后的数组按非降序排序
    dmin = 整数最大值
    for i from 0 to n-2:
        diff = 第i+1个元素 - 第i个元素
        if diff < dmin:
            dmin = diff
            if dmin == 0:  // 差值为0时提前终止，无法更小
                释放内存并返回dmin
    释放内存并返回dmin

修正后的C语言实现 #

// qsort的比较函数，用于整数排序
int compareInt(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

// 优化O(nlogn)复杂度算法（修正后）
int pair2(int A[], int n) {
    if (n < 2) return -1;
    
    // 复制原数组，避免修改输入数组
    int *temp = (int*)malloc(n * sizeof(int));
    if (!temp) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < n; i++) {
        temp[i] = A[i];
    }
    
    // 调用标准库排序函数，时间复杂度O(nlogn)
    qsort(temp, n, sizeof(int), compareInt);
    
    int dmin = INT_MAX;
    for (int i = 0; i < n - 1; i++) {
        int diff = temp[i+1] - temp[i];
        if (diff < dmin) {
            dmin = diff;
            if (dmin == 0) { // 提前终止，差值为0已是最小值
                free(temp);
                return dmin;
            }
        }
    }
    
    free(temp);
    return dmin;
}

常见逻辑问题修正说明：

• 补充了输入数组的复制操作，避免修改原数组
• 修复了循环边界（遍历到n-2而非n-1）
• 添加了差值为0时的提前终止逻辑，优化性能
• 完善了内存分配失败的错误处理

3. 测试方案与结果 #

测试设置 #

• 硬件环境：x86_64 CPU、16GB内存
• 编译环境：GCC 9.4.0，编译选项-O2
• 测试数组：对60000、70000、80000、90000、100000五个规模，各生成10组元素范围为[0, 10^9]的随机整数数组
• 计时方式：使用clock()统计CPU耗时，取10组测试的时间均值

测试结果示例 #

趋势说明：pair1耗时随数组规模平方增长，pair2耗时随规模呈线性对数增长，当数组规模超过60000后，两者性能差距急剧扩大。

测试代码框架 #

#include <time.h>

// 生成随机整数数组
void generateRandomArray(int A[], int n) {
    srand(time(NULL) + rand()); // 增加随机性
    for (int i = 0; i < n; i++) {
        A[i] = rand() % 1000000000;
    }
}

// 统计函数执行耗时（毫秒）
double testFunction(int (*func)(int[], int), int A[], int n) {
    clock_t start = clock();
    func(A, n);
    clock_t end = clock();
    return (double)(end - start) * 1000 / CLOCKS_PER_SEC;
}

int main() {
    int sizes[] = {60000, 70000, 80000, 90000, 100000};
    int num_sizes = sizeof(sizes)/sizeof(sizes[0]);
    int num_tests = 10;

    for (int s = 0; s < num_sizes; s++) {
        int n = sizes[s];
        int *A = (int*)malloc(n * sizeof(int));
        if (!A) {
            perror("malloc failed");
            exit(EXIT_FAILURE);
        }
        
        double pair1_total = 0, pair2_total = 0;
        for (int t = 0; t < num_tests; t++) {
            generateRandomArray(A, n);
            pair1_total += testFunction(pair1, A, n);
            pair2_total += testFunction(pair2, A, n);
            
            // 验证两个算法结果一致
            int res1 = pair1(A, n);
            int res2 = pair2(A, n);
            if (res1 != res2) {
                printf("Test %d for size %d failed: res1=%d, res2=%d\n", t, n, res1, res2);
                exit(EXIT_FAILURE);
            }
        }
        
        printf("数组规模：%d\n", n);
        printf("pair1平均耗时：%.2f ms\n", pair1_total / num_tests);
        printf("pair2平均耗时：%.2f ms\n\n", pair2_total / num_tests);
        
        free(A);
    }
    
    return 0;
}

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