四大基础排序算法
排序算法是编程世界的基石，本文深入讲解四种最基础、最常用的排序算法：冒泡排序、快速排序、插入排序和选择排序。
1. 冒泡排序
算法思想：
重复遍历数组，比较相邻元素，如果顺序错误就交换，使得较大元素逐渐到数组末尾。
//冒泡排序voidBubble_Sort(intarr[],intlen){for(inti=0;i<len-1;i++){for(intj=0;j<len-1-i;j++){if(arr[j+1]<arr[j]){inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}}| 适用场景 | 不适用场景 |
|---|---|
| 教学演示和理解排序原理 | 大规模数据排序 |
| 小规模数据（n<100） | 性能要求高的场景 |
| 数据基本有序 | 需要处理复杂对象的场景 |
常见错误总结：
- 数组越界：必须确保内层循环条件是
j<len-1-i - 忘记使用临时变量：直接交换会导致数据丢失
2. 快速排序
算法思想：
选择一个基准元素，将数组分为两部分，左边都小于基准，右边都大于基准，然后递归排序左右两部分。
// 交换两个元素voidswap(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}// 分区函数 - 快速排序的核心intpartition(intarr[],intlow,inthigh){// 选择最后一个元素作为基准intpivot=arr[high];// i 指向小于基准的区域的最后一个位置inti=low-1;// 遍历数组for(intj=low;j<high;j++){// 如果当前元素小于等于基准if(arr[j]<=pivot){i++;// 扩展小于基准的区域swap(&arr[i],&arr[j]);// 将当前元素放到小于基准的区域}}// 将基准放到正确位置（i+1）swap(&arr[i+1],&arr[high]);// 返回基准的最终位置returni+1;}// 快速排序voidQuick_Sort(intarr[],intlow,inthigh){if(low<high){// pi 是基准的最终位置intpi=partition(arr,low,high);// 递归排序左右两部分Quick_Sort(arr,low,pi-1);// 左半部分Quick_Sort(arr,pi+1,high);// 右半部分}}| 适用场景 | 不适用排序 |
|---|---|
| 大规模数据排序 | 小数据量排序（n<20） |
| 对平均性能要求高且内存有限的场景 | 数据基本有序 |
| 不需要稳定排序 | 需要稳定排序 |
3. 插入排序
算法思想：
将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置。
//插入排序voidinsertionSort(intarr[],intn){for(inti=1;i<n;i++){intkey=arr[i];// 当前要插入的元素intj=i-1;// 将比key大的元素向后移动while(j>=0&&arr[j]>key){arr[j+1]=arr[j];j--;}// 插入key到正确位置arr[j+1]=key;}}| 适用场景 | 不适用场景 |
|---|---|
| 小规模数据（n<50） | 大规模随机数据（n>1000） |
| 数据基本有序 | 逆序或高度无序数据 |
| 链表排序 | 性能要求极高的场景 |
4. 选择排序
算法思想：
每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。
//选择排序voidselectionSort(intarr[],intn){for(inti=0;i<n-1;i++){// 假设当前位置是最小值intminIndex=i;// 在未排序部分查找真正的最小值for(intj=i+1;j<n;j++){if(arr[j]<arr[minIndex]){minIndex=j;}}// 将最小值交换到当前位置if(minIndex!=i){inttemp=arr[i];arr[i]=arr[minIndex];arr[minIndex]=temp;}}}| 适用场景 | 不适用场景 |
|---|---|
| 小规模数据 | 大规模数据（n>1000） |
| 交换成本高的情况 | 需要稳定排序 |
| 需要最少交换次数 | 数据基本有序 |
| 内存有限的嵌入式系统 | 性能要求高的场景 |
