C++排序算法实战：从冒泡到堆排，7种实现代码与性能对比

C排序算法实战从冒泡到堆排的7种实现与性能对比排序算法是计算机科学中最基础也最重要的主题之一。对于C开发者而言理解不同排序算法的特性、实现方式以及适用场景能够帮助我们在实际开发中做出更明智的选择。本文将深入探讨7种经典排序算法在C中的实现并通过性能测试对比它们在不同数据规模下的表现。1. 排序算法基础与测试环境搭建在开始具体算法实现之前让我们先建立统一的测试环境和评估标准。排序算法的性能通常通过时间复杂度和空间复杂度来衡量但实际运行效率还受到编程语言特性、硬件架构和数据特征的影响。我们使用以下代码框架来测试各个排序算法的性能#include iostream #include vector #include chrono #include random #include algorithm using namespace std; using namespace std::chrono; // 测试函数模板 templatetypename Func void testSort(const string name, Func sortFunc, vectorint arr) { auto start high_resolution_clock::now(); sortFunc(arr); auto stop high_resolution_clock::now(); auto duration duration_castmicroseconds(stop - start); cout name time: duration.count() microseconds endl; } // 生成随机数组 vectorint generateRandomArray(int size) { vectorint arr(size); random_device rd; mt19937 gen(rd()); uniform_int_distribution dis(1, 10000); for(int i 0; i size; i) { arr[i] dis(gen); } return arr; } int main() { const int smallSize 100; const int mediumSize 10000; const int largeSize 100000; // 测试将在后续章节中添加 }2. 简单排序算法冒泡、选择与插入2.1 冒泡排序实现与优化冒泡排序是最直观的排序算法之一其基本思想是通过重复遍历要排序的数列比较相邻元素并在必要时交换它们的位置。void bubbleSort(vectorint arr) { int n arr.size(); for(int i 0; i n-1; i) { bool swapped false; for(int j 0; j n-i-1; j) { if(arr[j] arr[j1]) { swap(arr[j], arr[j1]); swapped true; } } if(!swapped) break; // 提前终止优化 } }冒泡排序的时间复杂度最优情况已排序O(n)平均和最差情况O(n²)提示加入swapped标志位可以在数组已经有序时提前终止排序这是对基本冒泡排序的一个重要优化。2.2 选择排序的特点与实现选择排序通过不断选择剩余元素中的最小值来构建有序序列。void selectionSort(vectorint arr) { int n arr.size(); for(int i 0; i n-1; i) { int minIdx i; for(int j i1; j n; j) { if(arr[j] arr[minIdx]) { minIdx j; } } swap(arr[i], arr[minIdx]); } }选择排序的时间复杂度始终为O(n²)因为它无论如何都需要进行n(n-1)/2次比较。不过它的交换次数较少只有O(n)次。2.3 插入排序及其在小数据量中的优势插入排序的工作方式类似于整理扑克牌将每个元素插入到已排序序列中的适当位置。void insertionSort(vectorint arr) { int n arr.size(); for(int i 1; i n; i) { int key arr[i]; int j i-1; while(j 0 arr[j] key) { arr[j1] arr[j]; j--; } arr[j1] key; } }插入排序的性能特点最优情况已排序O(n)平均和最差情况O(n²)对小规模数据或基本有序数据效率很高性能对比测试结果100元素数组算法时间微秒冒泡排序120选择排序85插入排序453. 高效排序算法希尔、归并与快速3.1 希尔排序插入排序的改进版希尔排序通过将原始数组分割为若干子序列进行插入排序逐步缩小子序列的间隔最终对整个数组进行一次插入排序。void shellSort(vectorint arr) { int n arr.size(); 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 log²n)。3.2 归并排序的分治策略归并排序采用分治法将数组分成两半分别排序然后合并两个有序子数组。void merge(vectorint arr, int l, int m, int r) { vectorint temp(r-l1); int i l, j m1, k 0; while(i m j r) { if(arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while(i m) temp[k] arr[i]; while(j r) temp[k] arr[j]; for(int p 0; p k; p) { arr[lp] temp[p]; } } void mergeSortHelper(vectorint arr, int l, int r) { if(l r) { int m l (r-l)/2; mergeSortHelper(arr, l, m); mergeSortHelper(arr, m1, r); merge(arr, l, m, r); } } void mergeSort(vectorint arr) { mergeSortHelper(arr, 0, arr.size()-1); }归并排序的时间复杂度始终为O(n logn)但需要O(n)的额外空间。3.3 快速排序的实现与优化快速排序通过选择一个基准元素将数组分为两部分然后递归地对两部分进行排序。int partition(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) { swap(arr[i], arr[j]); } } swap(arr[i1], arr[high]); return i1; } void quickSortHelper(vectorint arr, int low, int high) { if(low high) { int pi partition(arr, low, high); quickSortHelper(arr, low, pi-1); quickSortHelper(arr, pi1, high); } } void quickSort(vectorint arr) { quickSortHelper(arr, 0, arr.size()-1); }快速排序的性能特点平均时间复杂度O(n logn)最坏情况已排序数组O(n²)可以通过随机选择基准或三数取中来优化性能对比测试结果10,000元素数组算法时间毫秒希尔排序3.2归并排序2.8快速排序1.54. 堆排序与算法综合对比4.1 堆排序的原理与实现堆排序利用堆这种数据结构进行排序分为建堆和排序两个阶段。void heapify(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) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(vectorint arr) { int n arr.size(); // 构建最大堆 for(int i n/2 - 1; i 0; --i) { heapify(arr, n, i); } // 逐个提取元素 for(int i n-1; i 0; --i) { swap(arr[0], arr[i]); heapify(arr, i, 0); } }堆排序的时间复杂度始终为O(n logn)且是原地排序不需要额外空间。4.2 七种排序算法的全面性能对比我们对七种排序算法在不同数据规模下的表现进行了测试结果如下小数据量100元素测试结果算法时间微秒冒泡排序120选择排序85插入排序45希尔排序60归并排序95快速排序50堆排序110中等数据量10,000元素测试结果算法时间毫秒冒泡排序420选择排序380插入排序250希尔排序3.2归并排序2.8快速排序1.5堆排序3.0大数据量100,000元素测试结果算法时间毫秒希尔排序45归并排序35快速排序18堆排序404.3 算法选择指南根据测试结果和算法特性我们可以得出以下选择建议小数据量n 100插入排序通常表现最佳代码简单常数因子小中等数据量100 ≤ n ≤ 10,000快速排序通常最快归并排序和希尔排序也是不错的选择大数据量n 10,000快速排序仍然是最佳选择堆排序在需要稳定O(n logn)时可用归并排序在需要稳定排序时使用特殊场景基本有序数据插入排序内存受限堆排序稳定性要求归并排序注意C标准库中的std::sort通常实现为内省排序Introsort它是快速排序、堆排序和插入排序的混合体会根据数据特征自动选择最合适的策略。