C/C 排序算法从入门到精通排序算法评价维度在开始之前先统一几个概念后面每个算法都会提到时间复杂度最好/平均/最坏情况直接决定你的数据量能不能扛得住。空间复杂度除了原数组外额外占用的内存递归栈也算。稳定性相等元素的相对顺序是否保持不变。稳定排序在按多关键字排序时很有用。原地性是否依赖额外数组。下面按**“从低效到高效”**的顺序讲但建议实际开发时直接跳过前三个。1. 冒泡排序Bubble Sort—— 入门必死思想每轮从头到尾两两比较把最大的元素“冒泡”到末尾。重复 n-1 轮。优化加一个swapped标记如果某一轮没有发生交换说明已经有序提前结束。复杂度最好 O(n)已有序带标记平均/最坏 O(n²)空间 O(1)稳定代码voidbubbleSort(intarr[],intn){for(inti0;in-1;i){boolswappedfalse;for(intj0;jn-1-i;j){if(arr[j]arr[j1]){std::swap(arr[j],arr[j1]);swappedtrue;}}if(!swapped)break;}}个人吐槽面试官让你写冒泡多半是想看你有没有优化意识。如果你直接写两层循环不加标记那基本就凉了。2. 选择排序Selection Sort—— 脑回路最直思想每轮找出剩余部分的最小值放到已排序部分的末尾。也就是每次选一个最小的“扔”到前面。复杂度不管什么情况都是 O(n²)因为每次都要遍历剩余部分找最小值。不稳定交换可能打乱相等元素的顺序。空间O(1)代码voidselectionSort(intarr[],intn){for(inti0;in-1;i){intminIdxi;for(intji1;jn;j){if(arr[j]arr[minIdx])minIdxj;}if(minIdx!i)std::swap(arr[i],arr[minIdx]);}}注意有人觉得选择排序比冒泡快因为交换次数少。但实际由于比较次数固定数据量大时一样拉胯。3. 插入排序Insertion Sort—— 打扑克牌时的整理方式思想将当前元素插入到前面已经有序的序列中的正确位置。从第二个元素开始往前“挪”到合适位置。复杂度最好 O(n)已有序平均/最坏 O(n²)空间 O(1)稳定优点对小规模数据n 50或基本有序的数据插入排序效率很高甚至优于快速排序。很多高级排序如 std::sort在递归到小数组时会改用插入排序。代码voidinsertionSort(intarr[],intn){for(inti1;in;i){intkeyarr[i];intji-1;while(j0arr[j]key){arr[j1]arr[j];j--;}arr[j1]key;}}4. 希尔排序Shell Sort—— 插入排序的“跳跃版”思想希尔排序是插入排序的改进。它通过一个“增量序列”将数组分成若干子序列分别进行插入排序逐步缩小增量直到 1。目的是让元素能快速跨越较大距离移动到正确位置。复杂度依赖于增量序列。最常用的是希尔增量n/2, n/4, … 1时间复杂度 O(n²)。使用 Hibbard 增量1,3,7,…2^k-1可达到 O(n^1.5)。目前已知较好的序列可达 O(n log² n)。稳定性不稳定因为跨子序列交换。空间O(1)代码希尔增量voidshellSort(intarr[],intn){for(intgapn/2;gap0;gap/2){for(intigap;in;i){inttemparr[i];intji;while(jgaparr[j-gap]temp){arr[j]arr[j-gap];j-gap;}arr[j]temp;}}}个人经验希尔排序在实际工程中很少单独使用但理解它的思想对理解“如何改进插入排序”有帮助。而且它的代码短有时在嵌入式环境里用它代替快排因为不用递归。5. 归并排序Merge Sort—— 稳定、可预测思想分治法。将数组分成两半分别排序然后合并两个有序子数组。递归到底层单个元素。复杂度所有情况 O(n log n)。空间 O(n)需要额外辅助数组。稳定。优点稳定时间复杂度始终优秀适合链表排序链表归并不需要额外空间。缺点是需要额外内存。代码递归 辅助数组voidmerge(intarr[],intleft,intmid,intright){intn1mid-left1;intn2right-mid;int*Lnewint[n1];int*Rnewint[n2];for(inti0;in1;i)L[i]arr[lefti];for(inti0;in2;i)R[i]arr[mid1i];inti0,j0,kleft;while(in1jn2){if(L[i]R[j])arr[k]L[i];elsearr[k]R[j];}while(in1)arr[k]L[i];while(jn2)arr[k]R[j];delete[]L;delete[]R;}voidmergeSort(intarr[],intleft,intright){if(leftright)return;intmidleft(right-left)/2;mergeSort(arr,left,mid);mergeSort(arr,mid1,right);merge(arr,left,mid,right);}注意这里为了清晰每次递归都 new/delete实际优化时可以传一个全局临时数组避免频繁申请释放。6. 快速排序Quick Sort—— 平均性能之王思想选择一个基准pivot将数组分为小于基准、等于基准、大于基准三部分经典是分两半然后递归处理左右部分。复杂度平均 O(n log n)最好 O(n log n)每次基准都能均分最坏 O(n²)已有序且选第一个或最后一个作基准空间 O(log n)递归栈不稳定优化手段三数取中取 left, mid, right 的中位数作为基准小数组改用插入排序尾递归优化代码经典左右指针 三数取中intmedianOfThree(intarr[],intleft,intright){intmidleft(right-left)/2;if(arr[left]arr[mid])std::swap(arr[left],arr[mid]);if(arr[left]arr[right])std::swap(arr[left],arr[right]);if(arr[mid]arr[right])std::swap(arr[mid],arr[right]);// 将中位数放到 right-1 位置作为哨兵std::swap(arr[mid],arr[right-1]);returnarr[right-1];}voidquickSort(intarr[],intleft,intright){if(leftright)return;// 小数组用插入排序这里省略实际可加 if (right - left 阈值)intpivotmedianOfThree(arr,left,right);intileft,jright-1;while(true){while(arr[i]pivot){}while(arr[--j]pivot){}if(ij)break;std::swap(arr[i],arr[j]);}std::swap(arr[i],arr[right-1]);// 将基准放到正确位置quickSort(arr,left,i-1);quickSort(arr,i1,right);}注意上面这种写法边界容易搞混我写了一种更简洁的 Lomuto 分区但效率稍低。实际推荐 Hoare 分区或直接用std::sort。另一种更易读的 Lomuto 分区intpartition(intarr[],intlow,inthigh){intpivotarr[high];// 选最后一个intilow-1;for(intjlow;jhigh;j){if(arr[j]pivot){i;std::swap(arr[i],arr[j]);}}std::swap(arr[i1],arr[high]);returni1;}voidquickSortLomuto(intarr[],intlow,inthigh){if(lowhigh){intpipartition(arr,low,high);quickSortLomuto(arr,low,pi-1);quickSortLomuto(arr,pi1,high);}}Lomuto 简单但若数组已有序退化为 O(n²)。所以生产环境一定要三数取中。7. 堆排序Heap Sort—— 不稳定的 O(n log n) 原地排序思想将数组看作完全二叉树构建最大堆然后反复取堆顶最大值放到末尾再调整堆。复杂度所有情况 O(n log n)空间 O(1)不稳定。优点原地、时间复杂度稳定适合需要最坏情况保证的场景比如实时系统。缺点是不稳定且常数较大比快排慢。代码voidheapify(intarr[],intn,inti){intlargesti;intleft2*i1;intright2*i2;if(leftnarr[left]arr[largest])largestleft;if(rightnarr[right]arr[largest])largestright;if(largest!i){std::swap(arr[i],arr[largest]);heapify(arr,n,largest);}}voidheapSort(intarr[],intn){// 建堆for(intin/2-1;i0;i--){heapify(arr,n,i);}// 一个个取堆顶for(intin-1;i0;i--){std::swap(arr[0],arr[i]);heapify(arr,i,0);}}各算法一句话总结抄作业版算法平均时间复杂度最好最坏空间稳定冒泡O(n²)O(n)O(n²)O(1)✅选择O(n²)O(n²)O(n²)O(1)❌插入O(n²)O(n)O(n²)O(1)✅希尔O(n^1.3~1.5)依赖增量O(n²)O(1)❌归并O(n log n)O(n log n)O(n log n)O(n)✅快速O(n log n)O(n log n)O(n²)O(log n)❌堆排序O(n log n)O(n log n)O(n log n)O(1)❌完整示例测试所有排序 计时下面给出一份可运行的 C 代码包含上述所有排序函数以及一个测试main随机生成数组并比较排序结果和耗时。注意为了方便我把所有函数写在了一起。实际使用时请根据需求选用。#includeiostream#includechrono#includecstdlib#includectime#includeiomanip#includealgorithm// for std::is_sortedusingnamespacestd;usingnamespacechrono;// ---------- 声明所有排序函数这里只列原型具体实现见上面 ----------voidbubbleSort(intarr[],intn);voidselectionSort(intarr[],intn);voidinsertionSort(intarr[],intn);voidshellSort(intarr[],intn);voidmergeSort(intarr[],intleft,intright);voidquickSortLomuto(intarr[],intlow,inthigh);voidheapSort(intarr[],intn);// 为了统一调用接口对归并和快速排序做包装voidmergeSortWrap(intarr[],intn){mergeSort(arr,0,n-1);}voidquickSortWrap(intarr[],intn){quickSortLomuto(arr,0,n-1);}// 测试函数拷贝数组排序打印耗时和结果是否正确voidtestSort(conststringname,void(*sortFunc)(int[],int),intarr[],intn){int*copyArrnewint[n];for(inti0;in;i)copyArr[i]arr[i];autostarthigh_resolution_clock::now();sortFunc(copyArr,n);autoendhigh_resolution_clock::now();autodurationduration_castmicroseconds(end-start);boolsortedis_sorted(copyArr,copyArrn);coutsetw(15)name : setw(8)duration.count() us, (sorted?✔ 正确:✘ 错误)endl;delete[]copyArr;}intmain(){constintN10000;// 数据量可自行修改int*arrnewint[N];srand(time(nullptr));for(inti0;iN;i)arr[i]rand()%100000;cout数据量: Nendl;cout------------------------------------endl;// 注意冒泡/选择/插入在 N10000 时可能很慢如果嫌等太久可以减小 N 或注释掉// testSort(冒泡排序, bubbleSort, arr, N);// testSort(选择排序, selectionSort, arr, N);// testSort(插入排序, insertionSort, arr, N);testSort(希尔排序,shellSort,arr,N);testSort(归并排序,mergeSortWrap,arr,N);testSort(快速排序,quickSortWrap,arr,N);testSort(堆排序,heapSort,arr,N);delete[]arr;return0;}运行结果示例N10000单位微秒依机器不同而异数据量: 10000 ------------------------------------ 希尔排序 : 1523 us, ✔ 正确 归并排序 : 2341 us, ✔ 正确 快速排序 : 1056 us, ✔ 正确 堆排序 : 1876 us, ✔ 正确你可以把冒泡、选择、插入的注释去掉但建议把 N 降到 1000否则你可能真的要去泡杯咖啡。写在最后如果你只记住一个排序记住快速排序但务必实现三数取中。如果你需要稳定性且内存不是瓶颈归并排序是最稳妥的选择。如果你在嵌入式环境或不允许递归堆排序或希尔排序。如果数据量极小 50插入排序反而最快因为它没有递归开销且 cache 友好。实际开发中C 的std::sort是混合排序IntroSort —— 快速排序 堆排序 插入排序你不需要自己写但理解原理能帮你避开坑比如对已有序数据使用快速排序不加优化就会跌入最坏情况。最后如果发现哪里有错误欢迎指正毕竟我写这篇的时候也踩了几个边界条件的坑。排序算法虽然基础但写对不易共勉。