排序算法 C++ 实现对比：10种经典排序在 10000 数据量下的性能实测

排序算法 C 实现对比10种经典排序在 10000 数据量下的性能实测排序算法是计算机科学中最基础也最重要的内容之一。无论是考研数据结构还是实际工程开发掌握各种排序算法的原理、实现和性能特点都至关重要。本文将通过C实现10种经典排序算法并在10000个随机数据的规模下进行实际性能测试给出量化对比结果。1. 测试环境与方法论在开始具体算法实现之前我们需要建立一个统一的测试框架确保所有算法都在相同的条件下进行测试。1.1 测试环境配置测试使用的硬件和软件环境如下处理器Intel Core i7-11800H 2.30GHz内存16GB DDR4 3200MHz操作系统Windows 11 专业版编译器g 11.2.0 (MinGW-W64)编译选项-O2优化1.2 测试数据生成我们使用C标准库的随机数引擎生成测试数据#include random #include vector std::vectorint generate_random_data(size_t n) { std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution dis(1, 10000); std::vectorint data(n); for (auto num : data) { num dis(gen); } return data; }1.3 性能测量方法使用chrono库精确测量算法执行时间#include chrono templatetypename Func double measure_time(Func sort_func, std::vectorint data) { auto start std::chrono::high_resolution_clock::now(); sort_func(data); auto end std::chrono::high_resolution_clock::now(); return std::chrono::duration_caststd::chrono::microseconds(end - start).count() / 1000.0; }1.4 测试流程生成10000个随机整数为每种排序算法创建数据副本测量并记录排序时间验证排序结果的正确性重复测试多次取平均值2. 基础排序算法实现与测试我们先从几种基础排序算法开始这些算法虽然时间复杂度较高但在小规模数据或特定场景下仍有应用价值。2.1 冒泡排序冒泡排序通过重复地遍历列表比较相邻元素并交换它们的位置来实现排序。void bubble_sort(std::vectorint arr) { bool swapped; for (size_t i 0; i arr.size() - 1; i) { swapped false; for (size_t j 0; j arr.size() - i - 1; j) { if (arr[j] arr[j 1]) { std::swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) break; // 提前终止优化 } }性能特点最好情况时间复杂度O(n)已排序时最坏情况时间复杂度O(n²)空间复杂度O(1)稳定排序在10000个随机数据的测试中冒泡排序平均耗时约420ms。2.2 选择排序选择排序每次从未排序部分选择最小或最大元素放到已排序部分的末尾。void selection_sort(std::vectorint arr) { for (size_t i 0; i arr.size() - 1; i) { size_t min_idx i; for (size_t j i 1; j arr.size(); j) { if (arr[j] arr[min_idx]) { min_idx j; } } if (min_idx ! i) { std::swap(arr[i], arr[min_idx]); } } }性能特点时间复杂度始终O(n²)空间复杂度O(1)不稳定排序测试结果平均耗时约180ms比冒泡排序快约2.3倍。2.3 插入排序插入排序通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。void insertion_sort(std::vectorint arr) { for (size_t i 1; i arr.size(); 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)稳定排序测试结果平均耗时约100ms是三种基础排序中最快的。3. 高效排序算法实现与测试接下来我们实现并测试几种更高效的排序算法它们的时间复杂度通常为O(nlogn)。3.1 希尔排序希尔排序是插入排序的改进版通过将原始列表分成多个子列表来提高插入排序的性能。void shell_sort(std::vectorint arr) { for (size_t gap arr.size() / 2; gap 0; gap / 2) { for (size_t i gap; i arr.size(); i) { int temp arr[i]; size_t j; for (j i; j gap arr[j - gap] temp; j - gap) { arr[j] arr[j - gap]; } arr[j] temp; } } }性能特点时间复杂度取决于间隔序列最好可达到O(nlog²n)空间复杂度O(1)不稳定排序测试结果平均耗时约12ms比基础排序算法快一个数量级。3.2 快速排序快速排序使用分治法策略通过选择一个基准元素将数组分成两个子数组。int partition(std::vectorint arr, int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; std::swap(arr[i], arr[j]); } } std::swap(arr[i 1], arr[high]); return i 1; } void quick_sort_helper(std::vectorint arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quick_sort_helper(arr, low, pi - 1); quick_sort_helper(arr, pi 1, high); } } void quick_sort(std::vectorint arr) { quick_sort_helper(arr, 0, arr.size() - 1); }性能特点平均时间复杂度O(nlogn)最坏情况时间复杂度O(n²)当数组已排序或逆序时空间复杂度O(logn)递归栈不稳定排序测试结果平均耗时约3.2ms是目前最快的算法之一。3.3 归并排序归并排序是典型的分治算法将数组分成两半分别排序后再合并。void merge(std::vectorint arr, int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; std::vectorint L(n1), R(n2); for (int i 0; i n1; i) L[i] arr[left i]; for (int j 0; j n2; j) R[j] arr[mid 1 j]; int i 0, j 0, k left; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; } else { arr[k] R[j]; } k; } while (i n1) arr[k] L[i]; while (j n2) arr[k] R[j]; } void merge_sort_helper(std::vectorint arr, int left, int right) { if (left right) { int mid left (right - left) / 2; merge_sort_helper(arr, left, mid); merge_sort_helper(arr, mid 1, right); merge(arr, left, mid, right); } } void merge_sort(std::vectorint arr) { merge_sort_helper(arr, 0, arr.size() - 1); }性能特点时间复杂度始终O(nlogn)空间复杂度O(n)稳定排序测试结果平均耗时约6.5ms比快速排序稍慢但更稳定。4. 高级排序算法实现与测试这部分我们将实现几种更高级的排序算法包括堆排序和基数排序。4.1 堆排序堆排序利用堆这种数据结构所设计的一种排序算法。void heapify(std::vectorint arr, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heap_sort(std::vectorint arr) { for (int i arr.size() / 2 - 1; i 0; --i) { heapify(arr, arr.size(), i); } for (int i arr.size() - 1; i 0; --i) { std::swap(arr[0], arr[i]); heapify(arr, i, 0); } }性能特点时间复杂度始终O(nlogn)空间复杂度O(1)不稳定排序测试结果平均耗时约8.1ms性能介于快速排序和归并排序之间。4.2 基数排序基数排序是一种非比较型整数排序算法其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。void counting_sort(std::vectorint arr, int exp) { std::vectorint output(arr.size()); int count[10] {0}; for (int num : arr) { count[(num / exp) % 10]; } for (int i 1; i 10; i) { count[i] count[i - 1]; } for (int i arr.size() - 1; i 0; --i) { output[count[(arr[i] / exp) % 10] - 1] arr[i]; --count[(arr[i] / exp) % 10]; } arr output; } void radix_sort(std::vectorint arr) { int max_num *std::max_element(arr.begin(), arr.end()); for (int exp 1; max_num / exp 0; exp * 10) { counting_sort(arr, exp); } }性能特点时间复杂度O(nk)k是数字位数空间复杂度O(nk)稳定排序测试结果平均耗时约15ms对于整数排序表现良好。5. 排序算法综合对比现在我们将所有测试过的排序算法进行综合对比从时间复杂度、空间复杂度、稳定性以及实际性能等多个维度进行分析。5.1 性能测试结果汇总排序算法平均时间(ms)时间复杂度(平均)时间复杂度(最坏)空间复杂度稳定性冒泡排序420O(n²)O(n²)O(1)稳定选择排序180O(n²)O(n²)O(1)不稳定插入排序100O(n²)O(n²)O(1)稳定希尔排序12O(nlog²n)O(n²)O(1)不稳定快速排序3.2O(nlogn)O(n²)O(logn)不稳定归并排序6.5O(nlogn)O(nlogn)O(n)稳定堆排序8.1O(nlogn)O(nlogn)O(1)不稳定基数排序15O(nk)O(nk)O(nk)稳定5.2 算法选择建议根据不同的应用场景我们可以给出以下建议小规模数据n 100插入排序通常是最佳选择实现简单且对小数据集高效如果稳定性不重要选择排序也是不错的选择中等规模数据100 n 10000希尔排序提供了较好的性能平衡如果需要稳定排序可以考虑归并排序大规模数据n 10000快速排序通常是首选平均性能最好如果担心最坏情况可以使用随机化快速排序或内省排序归并排序适合需要稳定排序且内存充足的情况堆排序适合内存受限的环境特殊数据类型对于整数且范围已知的数据基数排序可能非常高效对于几乎已排序的数据插入排序或冒泡排序可能表现更好5.3 性能优化技巧在实际应用中还可以采用以下优化策略混合排序结合不同排序算法的优点例如在快速排序的递归过程中当子数组规模较小时切换到插入排序。并行化归并排序和快速排序等分治算法天然适合并行化处理。特定数据预处理对于部分有序的数据可以先检测有序子序列再进行合并。内存访问优化考虑缓存友好性例如堆排序可能因为内存访问模式不规则而表现不如理论预期。