C语言排序问题详解：从冒泡到快排的完整指南

1. 引言排序是C语言学习中最基础也最重要的算法之一。无论是处理学生成绩、商品价格还是任何需要有序展示的数据排序算法都扮演着核心角色。本文将带你系统梳理C语言中常见的排序算法从原理到代码实现帮助你彻底掌握排序问题。2. 冒泡排序Bubble Sort2.1 原理冒泡排序通过重复遍历待排序序列依次比较相邻两个元素如果顺序错误就交换它们。每一轮遍历都会把当前未排序部分的最大值冒泡到末尾。2.2 代码实现#includestdio.hvoidbubbleSort(intarr[],intn){for(inti0;in-1;i){// 每轮遍历将最大值冒泡到末尾for(intj0;jn-1-i;j){if(arr[j]arr[j1]){// 交换相邻元素inttemparr[j];arr[j]arr[j1];arr[j1]temp;}}}}intmain(){intarr[]{64,34,25,12,22,11,90};intnsizeof(arr)/sizeof(arr[0]);bubbleSort(arr,n);printf(排序后的数组\n);for(inti0;in;i){printf(%d ,arr[i]);}printf(\n);return0;}2.3 优化技巧可以增加一个标志位如果某一轮没有发生任何交换说明序列已经有序提前结束排序voidbubbleSortOptimized(intarr[],intn){for(inti0;in-1;i){intswapped0;// 标志位for(intj0;jn-1-i;j){if(arr[j]arr[j1]){inttemparr[j];arr[j]arr[j1];arr[j1]temp;swapped1;}}// 如果没有交换说明已有序if(swapped0)break;}}3. 选择排序Selection Sort3.1 原理选择排序每一轮从未排序部分选出最小值放到已排序部分的末尾。它的交换次数比冒泡排序少但比较次数相同。3.2 代码实现voidselectionSort(intarr[],intn){for(inti0;in-1;i){intminIndexi;// 记录最小值的下标for(intji1;jn;j){if(arr[j]arr[minIndex]){minIndexj;}}// 将最小值交换到当前位置if(minIndex!i){inttemparr[i];arr[i]arr[minIndex];arr[minIndex]temp;}}}4. 插入排序Insertion Sort4.1 原理插入排序像整理扑克牌一样将每个元素插入到前面已排序序列的正确位置。对于近乎有序的数据插入排序效率非常高。4.2 代码实现voidinsertionSort(intarr[],intn){for(inti1;in;i){intkeyarr[i];// 当前要插入的元素intji-1;// 将比 key 大的元素向后移动while(j0arr[j]key){arr[j1]arr[j];j--;}arr[j1]key;// 插入到正确位置}}5. 快速排序Quick Sort5.1 原理快速排序采用分治策略选择一个基准元素pivot将数组分成两部分左边都小于基准右边都大于基准然后递归地对两部分排序。它是实际应用中最常用的排序算法之一。5.2 代码实现// 分区函数返回基准元素的最终位置intpartition(intarr[],intlow,inthigh){intpivotarr[high];// 选择最后一个元素作为基准intilow-1;// i 指向小于基准的区域的末尾for(intjlow;jhigh;j){if(arr[j]pivot){i;// 交换 arr[i] 和 arr[j]inttemparr[i];arr[i]arr[j];arr[j]temp;}}// 将基准放到正确位置inttemparr[i1];arr[i1]arr[high];arr[high]temp;returni1;}voidquickSort(intarr[],intlow,inthigh){if(lowhigh){intpipartition(arr,low,high);quickSort(arr,low,pi-1);// 递归排序左半部分quickSort(arr,pi1,high);// 递归排序右半部分}}6. 归并排序Merge Sort6.1 原理归并排序同样采用分治策略将数组不断对半拆分直到每个子数组只有一个元素然后两两合并成有序数组。它的时间复杂度稳定为 O(n log n)适合大数据量排序。6.2 代码实现// 合并两个有序子数组voidmerge(intarr[],intleft,intmid,intright){intn1mid-left1;intn2right-mid;// 创建临时数组intL[n1],R[n2];for(inti0;in1;i)L[i]arr[lefti];for(intj0;jn2;j)R[j]arr[mid1j];inti0,j0,kleft;// 合并两个有序数组while(in1jn2){if(L[i]R[j]){arr[k]L[i];i;}else{arr[k]R[j];j;}k;}// 复制剩余元素while(in1){arr[k]L[i];i;k;}while(jn2){arr[k]R[j];j;k;}}voidmergeSort(intarr[],intleft,intright){if(leftright){intmidleft(right-left)/2;mergeSort(arr,left,mid);// 排序左半部分mergeSort(arr,mid1,right);// 排序右半部分merge(arr,left,mid,right);// 合并}}7. 排序算法对比算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定8. 实战完整排序程序下面是一个综合示例演示如何用函数指针灵活切换不同的排序算法#includestdio.h#includestdlib.h// 各种排序函数声明实现见上文voidbubbleSort(intarr[],intn);voidselectionSort(intarr[],intn);voidinsertionSort(intarr[],intn);voidquickSort(intarr[],intlow,inthigh);voidmergeSort(intarr[],intleft,intright);// 打印数组voidprintArray(intarr[],intn){for(inti0;in;i){printf(%d ,arr[i]);}printf(\n);}intmain(){intarr[]{64,34,25,12,22,11,90};intnsizeof(arr)/sizeof(arr[0]);printf(原始数组\n);printArray(arr,n);// 使用快速排序quickSort(arr,0,n-1);printf(快速排序结果\n);printArray(arr,n);return0;}9. 常见面试问题9.1 什么时候用哪种排序数据量小50插入排序或冒泡排序数据量中等快速排序平均性能最好数据量很大且要求稳定归并排序数据近乎有序插入排序接近 O(n)9.2 如何判断排序算法的稳定性稳定性指相同值的元素在排序后保持原有相对顺序。冒泡、插入、归并是稳定的选择、快速是不稳定的。10. 总结本文系统介绍了C语言中五种经典排序算法冒泡、选择、插入、快速和归并。每种算法都有其适用场景冒泡排序简单直观适合教学和小规模数据选择排序交换次数少适合交换代价高的场景插入排序对近乎有序的数据效率极高快速排序综合性能最优实际应用最广归并排序稳定且时间复杂度有保证适合大数据量建议初学者先吃透冒泡和插入排序再逐步掌握快速排序和归并排序。多动手写代码、多调试才能真正理解每种算法的精髓。