为何实现的插入排序比归并排序更快？求正确代码计时方法

一、测试结果不符的核心原因 #

你的猜测完全正确——循环测试时未重置数组状态导致了反直觉的结果：

• 第一次排序后数组已完全有序，后续999次插入排序触发了最佳时间复杂度O(n)：仅需遍历数组，无需移动任何元素。
• 而归并排序无论数组是否有序，都会执行完整的分治合并流程，时间复杂度始终维持在O(n log n)，因此整体耗时更高。

正确的测试方式：

• 每次循环前重新生成随机无序数组（或复制原始未排序数组的副本），确保每次排序都针对无序输入执行。
• 若要验证最坏情况差异，可生成完全逆序的数组：此时插入排序时间复杂度升至O(n²)，归并排序仍稳定在O(n log n)，就能得到你预期的结果。

二、C语言正确计时方法 #

1. 标准库clock()（统计CPU执行时间） #

clock()返回程序启动后消耗的CPU时钟周期数，结合CLOCKS_PER_SEC可转换为秒，适合统计算法的CPU耗时：

#include <time.h>
#include <stdio.h>

int main() {
    clock_t start, end;
    double cpu_time;

    start = clock();
    // 执行排序逻辑（需确保每次循环重置数组）
    end = clock();

    cpu_time = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("CPU耗时：%.6f 秒\n", cpu_time);
    return 0;
}

2. gettimeofday()（统计墙钟时间，POSIX系统） #

若需统计包含等待时间的实际流逝时间，可使用gettimeofday()：

#include <sys/time.h>
#include <stdio.h>

int main() {
    struct timeval start, end;
    double elapsed_time;

    gettimeofday(&start, NULL);
    // 执行排序逻辑
    gettimeofday(&end, NULL);

    elapsed_time = (end.tv_sec - start.tv_sec) + 
                   (end.tv_usec - start.tv_usec) / 1000000.0;
    printf("实际耗时：%.6f 秒\n", elapsed_time);
    return 0;
}

3. clock_gettime()（高精度计时，POSIX标准） #

需要纳秒级精度时，推荐使用clock_gettime()，且选择CLOCK_MONOTONIC时钟避免系统时间调整的影响：

#include <time.h>
#include <stdio.h>

int main() {
    struct timespec start, end;
    double elapsed_time;

    clock_gettime(CLOCK_MONOTONIC, &start);
    // 执行排序逻辑
    clock_gettime(CLOCK_MONOTONIC, &end);

    elapsed_time = (end.tv_sec - start.tv_sec) + 
                   (end.tv_nsec - start.tv_nsec) / 1e9;
    printf("高精度耗时：%.9f 秒\n", elapsed_time);
    return 0;
}

编译时需链接实时库（部分新系统可省略）：gcc your_code.c -o your_program -lrt

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