C语言算法专题总结（一）排序

C 语言排序算法专题总结一、冒泡排序Bubble Sort基本思想比较相邻两个数的大小每一趟将最大数冒至数组末尾。优化策略若某一趟没有进行交换则说明已经有序可以设置 flag 提前停止。代码实现voidbubbleSort(inta[],intn){for(inti0;in-1;i){for(intj0;jn-i-1;j){if(a[j]a[j1]){inttmpa[j];a[j]a[j1];a[j1]tmp;}}}}时间复杂度最好情况O(n) - 已经有序平均情况O(n²)最坏情况O(n²)空间复杂度O(1)稳定性稳定排序二、选择排序Selection Sort基本思想每一趟在未排序部分中选择最小的数放在已排序部分的末尾。代码实现voidselectionSort(inta[],intn){for(inti0;in;i){intminIndexi;// 找到最小值的索引for(intji1;jn;j){if(a[minIndex]a[j]){minIndexj;}}// 交换inttmpa[i];a[i]a[minIndex];a[minIndex]tmp;}}时间复杂度最好、平均、最坏情况O(n²)空间复杂度O(1)稳定性不稳定排序三、插入排序Insertion Sort基本思想前 i 个数字是已排序的部分将第 i1 个数字插入到前面已排序序列的适当位置。代码实现voidinsertionSort(inta[],intn){for(inti1;in;i){intkeya[i],ji;// 比 key 大的元素向后移动while(j0keya[j-1]){a[j]a[j-1];j--;}a[j]key;}}时间复杂度最好情况O(n) - 已经有序平均情况O(n²)最坏情况O(n²)空间复杂度O(1)稳定性稳定排序四、快速排序Quick Sort基本思想采用分治法选定一个基准元素pivot将数组分为两部分左侧都比基准小右侧都比基准大然后递归排序两部分。代码实现// 分区函数intpartition(inta[],intlow,inthigh){intkeya[low];// 选择第一个元素作为基准while(lowhigh){// 从右向左找小于基准的元素while(a[high]keylowhigh)high--;a[low]a[high];// 从左向右找大于基准的元素while(a[low]keylowhigh)low;a[high]a[low];}a[low]key;returnlow;}// 快速排序主函数voidquickSort(inta[],intn,intlow,inthigh){if(lowhigh){intpivotkeypartition(a,low,high);quickSort(a,n,low,pivotkey-1);// 左半部分quickSort(a,n,pivotkey1,high);// 右半部分}}使用库函数 qsort#includestdlib.h// 比较函数intcompare(constvoid*a,constvoid*b){intnum1*((int*)a);intnum2*((int*)b);returnnum1-num2;// 升序}// 调用示例qsort(arr,n,sizeof(int),compare);自定义排序规则示例// 西电考题按各位数字之和降序排列和相等时按数字本身升序intsumOfDigits(intnum){intsum0;while(num0){sumnum%10;num/10;}returnsum;}intcompare(constvoid*a,constvoid*b){intnum1*((int*)a);intnum2*((int*)b);intsum1sumOfDigits(num1);intsum2sumOfDigits(num2);if(sum1sum2){returnnum1-num2;// 和相等时按数字升序}else{returnsum2-sum1;// 按数字和降序}}时间复杂度最好情况O(n log n)平均情况O(n log n)最坏情况O(n²) - 已经有序时空间复杂度O(log n) - 递归栈稳定性不稳定排序五、归并排序Merge Sort基本思想采用分治法将数组分为两部分分别排序然后合并两个有序序列。代码实现// 合并两个有序子序列voidmerge(inta[],intlow,intmid,inthigh){intilow,jmid1,k0;int*temp(int*)malloc((high-low1)*sizeof(int));// 比较两个子序列的元素较小的放入临时数组while(imidjhigh){if(a[i]a[j]){temp[k]a[i];}else{temp[k]a[j];}}// 复制剩余元素while(imid)temp[k]a[i];while(jhigh)temp[k]a[j];// 将临时数组复制回原数组for(i0;ihigh-low1;i){a[lowi]temp[i];}free(temp);}// 归并排序主函数voidmergeSort(inta[],intlow,inthigh){if(lowhigh){intmidlow(high-low)/2;mergeSort(a,low,mid);// 左半部分mergeSort(a,mid1,high);// 右半部分merge(a,low,mid,high);// 合并}}时间复杂度最好、平均、最坏情况O(n log n)空间复杂度O(n) - 需要额外空间稳定性稳定排序特点常考稳定性适合链表排序六、堆排序Heap Sort基本思想基于堆数据结构完全二叉树构建大根堆/小根堆后进行排序。代码实现// 堆化函数维护以 i 为根的子树满足大根堆性质voidheapify(inta[],intn,inti){intlargesti;intlefti*21;// 左孩子intrighti*22;// 右孩子// 找出父节点和两个孩子中的最大值if(leftna[largest]a[left])largestleft;if(rightna[largest]a[right])largestright;if(largest!i){// 交换inttmpa[i];a[i]a[largest];a[largest]tmp;// 递归调整被影响的子树heapify(a,n,largest);}}// 堆排序主函数voidheapSort(inta[],intn){// 构建初始大根堆for(intin/2-1;i0;i--){heapify(a,n,i);}// 依次将堆顶元素与末尾元素交换for(intin-1;i0;i--){inttmpa[0];a[0]a[i];a[i]tmp;// 重新调整堆heapify(a,i,0);}}时间复杂度最好、平均、最坏情况O(n log n)空间复杂度O(1)稳定性不稳定排序七、基数排序Radix Sort基本思想按照低位优先LSD或高位优先MSD的方式逐位进行排序。通常配合计数排序使用。代码实现// 计数排序辅助函数按指定位数排序voidcountingSortForRadix(intarr[],intn,intexp){intoutput[n],count[10]{0};// 统计当前位的基数for(inti0;in;i){count[(arr[i]/exp)%10];}// 累加基数for(inti1;i10;i){count[i]count[i-1];}// 从后往前放置元素保证稳定性for(intin-1;i0;i--){output[count[(arr[i]/exp)%10]-1]arr[i];count[(arr[i]/exp)%10]--;}// 复制回原数组for(inti0;in;i){arr[i]output[i];}}// 基数排序主函数voidradixSort(intarr[],intn){// 找出最大值确定位数intmaxarr[0];for(inti1;in;i){if(arr[i]max)maxarr[i];}// 按每一位进行计数排序for(intexp1;max/exp0;exp*10){countingSortForRadix(arr,n,exp);}}时间复杂度O(d × (n k))d 为位数k 为基数通常为 10空间复杂度O(n k)稳定性稳定排序八、双向冒泡排序Cocktail Sort基本思想冒泡排序的改进版每一轮在两个方向上进行冒泡先从左到右将最大值移到右端再从右到左将最小值移到左端。代码实现voidcocktailSort(intarr[],intn){intstart0,endn-1;while(startend){// 从左到右将最大值移到右端for(intistart;iend;i){if(arr[i]arr[i1]){inttmparr[i];arr[i]arr[i1];arr[i1]tmp;}}end--;// 从右到左将最小值移到左端for(intiend;istart;i--){if(arr[i]arr[i-1]){inttmparr[i];arr[i]arr[i-1];arr[i-1]tmp;}}start;}}时间复杂度最好情况O(n)平均情况O(n²)最坏情况O(n²)空间复杂度O(1)稳定性稳定排序九、统一测试代码以下代码可以用来测试上述所有排序算法只需替换调用的排序函数即可#includestdio.h#includestdlib.h// 函数声明voidbubbleSort(inta[],intn);// 冒泡排序voidselectionSort(inta[],intn);// 选择排序voidinsertionSort(inta[],intn);// 插入排序voidquickSort(inta[],intn,intlow,inthigh);// 快速排序voidmergeSort(inta[],intlow,inthigh);// 归并排序voidheapSort(inta[],intn);voidradixSort(intarr[],intn);voidcocktailSort(intarr[],intn);intmain(){intn;printf(请输入数字的个数:);scanf(%d,n);// 动态分配内存int*arr(int*)malloc(n*sizeof(int));if(arrNULL){printf(内存分配失败\n);return0;}printf(请输入%d个数字:,n);for(inti0;in;i){scanf(%d,arr[i]);}// 对数组进行从小到大的排序// 可以替换为以下任意排序函数// bubbleSort(arr, n); // 冒泡排序// selectionSort(arr, n); // 选择排序// insertionSort(arr, n); // 插入排序// quickSort(arr, n, 0, n-1); // 快速排序// mergeSort(arr, 0, n-1); // 归并排序// heapSort(arr, n); // 堆排序// radixSort(arr, n); // 基数排序cocktailSort(arr,n);// 双向冒泡排序// 输出排序结果for(inti0;in;i){printf(%d ,arr[i]);}// 释放内存free(arr);return0;}使用说明编译时需要将所有排序函数的实现代码一起编译通过注释/取消注释不同的排序函数调用来测试不同算法快速排序调用quickSort(arr, n, 0, n-1)归并排序调用mergeSort(arr, 0, n-1)十、各种排序算法对比排序算法最好时间平均时间最坏时间空间复杂度稳定性适用场景冒泡排序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 log n)O(n log n)O(n²)O(log n)不稳定大规模数据、一般情况首选归并排序O(n log n)O(n log n)O(n log n)O(n)稳定要求稳定性、链表排序堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定要求最坏情况也是 O(n log n)基数排序O(d×n)O(d×n)O(d×n)O(nk)稳定整数排序、位数固定双向冒泡O(n)O(n²)O(n²)O(1)稳定数据量小、基本有序十一、排序算法选择建议1. 小规模数据n ≤ 50推荐插入排序、冒泡排序理由简单易懂常数因子小2. 大规模数据一般情况快速排序效率最高要求稳定性归并排序要求最坏情况好堆排序3. 特殊场景基本有序插入排序、冒泡排序整数排序且范围已知基数排序、计数排序链表排序归并排序内存受限堆排序、原地排序4. 考试重点稳定性判断归并、插入、冒泡、基数是稳定的时间复杂度分析重点掌握快排、归并、堆排序实际应用qsort 库函数的使用十二、常见问题1. 如何判断排序算法的稳定性答如果排序后相同元素的相对位置不变则为稳定排序。例如[3a, 1, 3b, 2]排序后为[1, 2, 3a, 3b]3a 仍在 3b 前面。2. 快速排序为什么不稳定答因为在分区过程中可能会跨越多个位置交换元素导致相同元素的相对位置改变。3. 归并排序为什么稳定答因为在合并时当两个元素相等时优先选择左边子序列的元素保持了原有顺序。4. 如何选择基准元素快速排序答固定位置如第一个、最后一个随机选择三数取中首、中、尾的中位数5. 堆排序中建堆的时间复杂度答O(n)不是 O(n log n)。因为大部分节点的高度较小。