C语言八大排序算法性能实测：10万数据下快排与堆排序耗时对比

C语言八大排序算法性能实测：10万数据下快排与堆排序耗时对比

排序算法是计算机科学中最基础也最重要的算法之一。对于C语言开发者来说，深入理解各种排序算法的性能特点，能够在实际开发中做出更合理的选择。本文将通过实测对比八大经典排序算法在10万随机整数排序场景下的性能表现，特别是快速排序与堆排序的耗时差异。

1. 测试环境与方法论

为了确保测试结果的准确性和可重复性，我们搭建了统一的测试框架：

#include <stdio.h> #include <stdlib.h> #include <time.h> #define DATA_SIZE 100000 // 生成随机数组 void generate_random_array(int arr[], int size) { for(int i=0; i<size; i++) { arr[i] = rand() % DATA_SIZE; } } // 测试排序算法耗时 void test_sort(void (*sort_func)(int[], int), int arr[], int size) { clock_t start = clock(); sort_func(arr, size); clock_t end = clock(); double elapsed = (double)(end - start) / CLOCKS_PER_SEC; printf("耗时: %.4f秒\n", elapsed); }

测试采用以下标准：

• 数据规模：10万个随机整数（范围0-99999）
• 测试平台：Intel i7-10750H @ 2.60GHz，16GB内存
• 编译器：GCC 9.3.0，优化级别-O2
• 每种算法运行5次取平均值

2. 八大排序算法实现与原理

2.1 冒泡排序

冒泡排序通过重复遍历列表，比较相邻元素并交换顺序错误的元素。其特点是实现简单但效率低下。

void bubble_sort(int arr[], int n) { for(int i=0; i<n-1; i++) { int swapped = 0; for(int j=0; j<n-i-1; j++) { if(arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; swapped = 1; } } if(!swapped) break; } }

性能特点：

• 时间复杂度：最好O(n)，最坏O(n²)
• 空间复杂度：O(1)
• 稳定性：稳定

2.2 选择排序

选择排序每次从未排序部分选择最小元素放到已排序部分的末尾。

void selection_sort(int arr[], int n) { for(int i=0; i<n-1; i++) { int min_idx = i; for(int j=i+1; j<n; j++) { if(arr[j] < arr[min_idx]) { min_idx = j; } } if(min_idx != i) { int temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp; } } }

性能特点：

• 时间复杂度：始终O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定

2.3 插入排序

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

void insertion_sort(int arr[], int n) { for(int i=1; i<n; i++) { int key = arr[i]; int j = i-1; while(j>=0 && arr[j]>key) { arr[j+1] = arr[j]; j--; } arr[j+1] = key; } }

性能特点：

• 时间复杂度：最好O(n)，最坏O(n²)
• 空间复杂度：O(1)
• 稳定性：稳定

2.4 希尔排序

希尔排序是插入排序的改进版，通过将原始列表分割为若干子列表进行插入排序，最终对整个列表进行插入排序。

void shell_sort(int arr[], int n) { for(int gap=n/2; gap>0; gap/=2) { for(int i=gap; i<n; i++) { int temp = arr[i]; int j; for(j=i; j>=gap && arr[j-gap]>temp; j-=gap) { arr[j] = arr[j-gap]; } arr[j] = temp; } } }

性能特点：

• 时间复杂度：O(n^(3/2))到O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定

2.5 归并排序

归并排序采用分治法，将列表分为两半，分别排序后再合并。

void merge(int arr[], int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for(int i=0; i<n1; i++) L[i] = arr[l+i]; for(int j=0; j<n2; j++) R[j] = arr[m+1+j]; int i=0, j=0, k=l; while(i<n1 && j<n2) { if(L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while(i < n1) arr[k++] = L[i++]; while(j < n2) arr[k++] = R[j++]; } void merge_sort(int arr[], int l, int r) { if(l < r) { int m = l + (r-l)/2; merge_sort(arr, l, m); merge_sort(arr, m+1, r); merge(arr, l, m, r); } }

性能特点：

• 时间复杂度：始终O(nlogn)
• 空间复杂度：O(n)
• 稳定性：稳定

2.6 快速排序

快速排序通过选择一个"基准"元素，将数组分为两部分，一部分小于基准，一部分大于基准，然后递归地对两部分进行排序。

int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for(int j=low; j<=high-1; j++) { if(arr[j] < pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; } void quick_sort(int arr[], int low, int high) { if(low < high) { int pi = partition(arr, low, high); quick_sort(arr, low, pi-1); quick_sort(arr, pi+1, high); } }

性能特点：

• 时间复杂度：最好O(nlogn)，最坏O(n²)
• 空间复杂度：O(logn)
• 稳定性：不稳定

2.7 堆排序

堆排序利用堆这种数据结构所设计的一种排序算法，通过构建最大堆或最小堆来实现排序。

void heapify(int arr[], int n, int i) { int largest = i; int l = 2*i + 1; int r = 2*i + 2; if(l < n && arr[l] > arr[largest]) largest = l; if(r < n && arr[r] > arr[largest]) largest = r; if(largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } void heap_sort(int arr[], int n) { for(int i=n/2-1; i>=0; i--) { heapify(arr, n, i); } for(int i=n-1; i>0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } }

性能特点：

• 时间复杂度：始终O(nlogn)
• 空间复杂度：O(1)
• 稳定性：不稳定

2.8 基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

int get_max(int arr[], int n) { int max = arr[0]; for(int i=1; i<n; i++) { if(arr[i] > max) max = arr[i]; } return max; } void count_sort(int arr[], int n, int exp) { int output[n]; int count[10] = {0}; for(int i=0; i<n; i++) { count[(arr[i]/exp)%10]++; } for(int i=1; i<10; i++) { count[i] += count[i-1]; } for(int i=n-1; i>=0; i--) { output[count[(arr[i]/exp)%10]-1] = arr[i]; count[(arr[i]/exp)%10]--; } for(int i=0; i<n; i++) { arr[i] = output[i]; } } void radix_sort(int arr[], int n) { int m = get_max(arr, n); for(int exp=1; m/exp>0; exp*=10) { count_sort(arr, n, exp); } }

性能特点：

• 时间复杂度：O(nk)
• 空间复杂度：O(n+k)
• 稳定性：稳定

3. 性能实测结果对比

我们对10万随机整数进行了排序测试，得到以下耗时数据：

从测试结果可以看出：

1. 快速排序表现最佳，平均耗时仅0.016秒
2. 堆排序紧随其后，耗时0.022秒
3. 归并排序表现稳定，耗时0.028秒
4. 基数排序对整数排序效果良好，耗时0.035秒
5. 希尔排序作为改进版插入排序，性能提升显著
6. 基础排序算法（冒泡、选择、插入）在大数据量下性能较差

4. 快排与堆排序深度对比

快速排序和堆排序都是高效的O(nlogn)排序算法，但在实际应用中存在显著差异：

4.1 时间复杂度对比

虽然两者平均时间复杂度相同，但实际表现有差异：

• 快速排序：

  • 平均情况：O(nlogn)
  • 最坏情况：O(n²)（当输入已排序或逆序时）
  • 分区操作效率高，常数因子小

• 堆排序：

  • 所有情况：O(nlogn)
  • 建堆过程O(n)，每次调整O(logn)
  • 常数因子较大，实际运行比快排慢

4.2 空间复杂度对比

• 快速排序：

  • 平均O(logn)的递归栈空间
  • 最坏O(n)的递归栈空间

• 堆排序：

  • 原地排序，O(1)额外空间
  • 适合内存受限环境

4.3 实际应用场景

选择快速排序当：

• 数据随机分布
• 对性能要求极高
• 有足够内存空间
• 不需要稳定排序

选择堆排序当：

• 需要保证最坏情况性能
• 内存空间有限
• 需要部分排序（如只取前k个元素）
• 数据量极大可能触发快排最坏情况

4.4 代码实现差异

快速排序的核心是分区操作：

int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for(int j=low; j<=high-1; j++) { if(arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i+1], &arr[high]); return i+1; }

堆排序的核心是堆调整：

void heapify(int arr[], int n, int i) { int largest = i; int l = 2*i + 1; int r = 2*i + 2; if(l < n && arr[l] > arr[largest]) largest = l; if(r < n && arr[r] > arr[largest]) largest = r; if(largest != i) { swap(&arr[i], &arr[largest]); heapify(arr, n, largest); } }

4.5 性能优化技巧

快速排序优化：

1. 三数取中法选择基准
2. 小数组切换为插入排序
3. 尾递归优化减少栈空间
4. 三向切分处理大量重复元素

堆排序优化：

1. 迭代方式实现heapify
2. 优化建堆过程
3. 特定场景下使用最小堆
4. 利用位运算加速索引计算

5. 排序算法选择指南

根据不同的应用场景，排序算法的选择应考虑以下因素：

5.1 数据规模

5.2 数据特征

5.3 稳定性要求

需要稳定排序的场景：

• 多关键字排序
• 需要保持原始相对顺序
• 排序结果作为其他算法的输入

5.4 内存限制

内存受限环境优先考虑：

• 堆排序（原地排序）
• 希尔排序（原地排序）
• 优化的快速排序（尾递归优化）

6. 测试框架完整代码

以下是完整的测试框架代码，可用于复现本文的测试结果：

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <string.h> #define DATA_SIZE 100000 void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void generate_random_array(int arr[], int size) { for(int i=0; i<size; i++) { arr[i] = rand() % DATA_SIZE; } } void test_sort(void (*sort_func)(int[], int), char *name, int arr[], int size) { int *test_arr = malloc(size * sizeof(int)); memcpy(test_arr, arr, size * sizeof(int)); clock_t start = clock(); sort_func(test_arr, size); clock_t end = clock(); double elapsed = (double)(end - start) / CLOCKS_PER_SEC; printf("%-12s: %.4f秒\n", name, elapsed); free(test_arr); } // 各排序算法实现(省略，见前文) int main() { srand(time(NULL)); int *data = malloc(DATA_SIZE * sizeof(int)); generate_random_array(data, DATA_SIZE); printf("排序算法性能测试(数据量:%d)\n", DATA_SIZE); printf("================================\n"); test_sort(bubble_sort, "冒泡排序", data, DATA_SIZE); test_sort(selection_sort, "选择排序", data, DATA_SIZE); test_sort(insertion_sort, "插入排序", data, DATA_SIZE); test_sort(shell_sort, "希尔排序", data, DATA_SIZE); // 归并排序需要特殊处理 void merge_sort_wrapper(int arr[], int n) { merge_sort(arr, 0, n-1); } test_sort(merge_sort_wrapper, "归并排序", data, DATA_SIZE); // 快速排序需要特殊处理 void quick_sort_wrapper(int arr[], int n) { quick_sort(arr, 0, n-1); } test_sort(quick_sort_wrapper, "快速排序", data, DATA_SIZE); test_sort(heap_sort, "堆排序", data, DATA_SIZE); test_sort(radix_sort, "基数排序", data, DATA_SIZE); free(data); return 0; }

7. 结论与工程实践建议

通过本次实测和分析，我们可以得出以下结论：

1. 快速排序在大多数随机数据场景下表现最优，是通用排序的首选算法
2. 堆排序提供了稳定的O(nlogn)性能，适合内存受限或需要保证最坏情况性能的场景
3. 归并排序稳定且性能可靠，适合需要稳定排序的大数据量场景
4. 基数排序对特定类型数据(如整数)有奇效，但适用场景有限
5. 基础排序算法仅适用于小规模数据或特定优化场景

在实际工程实践中，标准库的排序实现往往结合了多种优化策略。例如：

• C的qsort函数通常采用快速排序+插入排序的混合策略
• C++的std::sort采用内省排序(快速排序+堆排序)
• Java的Arrays.sort对基本类型使用快速排序变种，对对象使用归并排序

对于性能关键型应用，建议：

1. 优先使用语言标准库提供的排序函数
2. 针对特定数据特征选择或定制排序算法
3. 在排序前尽可能减少数据规模
4. 考虑并行化排序算法以利用多核优势