C语言标准库提供的qsort函数是通用的快速排序实现，在实际开发中经常被用来处理各类排序需求。了解它的算法性能表现，能够帮助开发者更合理地选择排序方案，也能加深对快速排序特性的理解。
性能测试的核心指标
对qsort函数做性能测试，主要关注以下几个核心指标：
- 排序耗时：不同数据规模下完成排序的总时间，是最直观的性能体现
- 比较次数：排序过程中元素比较的总次数，反映算法的比较开销
- 交换次数：排序过程中元素交换的总次数，反映算法的移动开销
- 不同数据场景下的表现：随机数据、升序数据、降序数据、重复数据场景下的性能差异
测试环境准备
为了保证测试结果的准确性，需要固定测试环境，避免其他进程干扰。测试前需要关闭不必要的后台程序，同时保证每次测试的代码编译优化等级一致，这里我们使用-O0优化等级避免编译器优化影响测试结果。
测试用例设计
我们需要设计多组测试用例，覆盖不同的数据场景和数据规模：
- 数据规模：分别测试1000、10000、100000、1000000个元素的情况
- 数据场景：随机无序数据、完全升序数据、完全降序数据、大量重复数据
测试代码实现
下面是完整的性能测试代码，使用clock函数统计排序耗时，同时自定义比较函数统计比较次数：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 全局变量统计比较次数
int compare_count = 0;
// 整数比较函数，同时统计比较次数
int int_compare(const void *a, const void *b) {
compare_count++;
int num1 = *(int *)a;
int num2 = *(int *)b;
if (num1 < num2) {
return -1;
} else if (num1 > num2) {
return 1;
} else {
return 0;
}
}
// 生成随机数据
void generate_random_data(int *arr, int n) {
for (int i = 0; i < n; i++) {
arr[i] = rand() % 1000000;
}
}
// 生成升序数据
void generate_asc_data(int *arr, int n) {
for (int i = 0; i < n; i++) {
arr[i] = i;
}
}
// 生成降序数据
void generate_desc_data(int *arr, int n) {
for (int i = 0; i < n; i++) {
arr[i] = n - i - 1;
}
}
// 生成大量重复数据
void generate_repeat_data(int *arr, int n) {
for (int i = 0; i < n; i++) {
arr[i] = 100;
}
}
// 性能测试函数
void test_qsort_performance(int *arr, int n, const char *data_type) {
// 复制原数组，避免修改原始数据
int *test_arr = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
test_arr[i] = arr[i];
}
compare_count = 0;
clock_t start_time = clock();
qsort(test_arr, n, sizeof(int), int_compare);
clock_t end_time = clock();
double time_used = (double)(end_time - start_time) / CLOCKS_PER_SEC * 1000; // 转换为毫秒
printf("数据规模：%d，数据类型：%sn", n, data_type);
printf("排序耗时：%.2f 毫秒n", time_used);
printf("比较次数：%dn", compare_count);
printf("------------------------n");
free(test_arr);
}
int main() {
// 设置随机数种子
srand(time(NULL));
// 定义测试的数据规模
int data_sizes[] = {1000, 10000, 100000, 1000000};
int size_count = sizeof(data_sizes) / sizeof(data_sizes[0]);
// 遍历所有数据规模
for (int i = 0; i < size_count; i++) {
int n = data_sizes[i];
int *arr = (int *)malloc(n * sizeof(int));
// 测试随机数据
generate_random_data(arr, n);
test_qsort_performance(arr, n, "随机数据");
// 测试升序数据
generate_asc_data(arr, n);
test_qsort_performance(arr, n, "升序数据");
// 测试降序数据
generate_desc_data(arr, n);
test_qsort_performance(arr, n, "降序数据");
// 测试重复数据
generate_repeat_data(arr, n);
test_qsort_performance(arr, n, "重复数据");
free(arr);
}
return 0;
}
测试结果分析
运行上述测试代码后，我们可以得到不同场景下的性能数据，以下是典型测试结果的特征：
- 随机数据场景下，qsort的时间复杂度接近O(n log n)，数据规模翻倍时耗时增长约1倍多
- 升序和降序数据场景下，部分实现版本的qsort可能出现性能退化，耗时明显高于随机数据场景
- 大量重复数据场景下，qsort的比较次数会明显增多，性能也会有所下降
测试注意事项
做qsort性能测试时需要注意以下几点：
- 每次测试前需要重新生成数据，避免前一次排序结果影响后续测试
- 多次测试取平均值，减少单次测试的偶然误差
- 测试大数量级数据时，注意内存占用，避免内存溢出
- 不同编译器实现的qsort可能存在差异，测试结果仅代表当前编译环境下的表现