企业官网建设流程全解析

1. 引言

排序是C语言学习中最基础也最重要的算法之一。无论是处理学生成绩、商品价格还是任何需要有序展示的数据，排序算法都扮演着核心角色。本文将带你系统梳理C语言中常见的排序算法，从原理到代码实现，帮助你彻底掌握排序问题。

2. 冒泡排序（Bubble Sort）

2.1 原理

冒泡排序通过重复遍历待排序序列，依次比较相邻两个元素，如果顺序错误就交换它们。每一轮遍历都会把当前未排序部分的最大值"冒泡"到末尾。

2.2 代码实现

#include<stdio.h>voidbubbleSort(intarr[],intn){for(inti=0;i<n-1;i++){// 每轮遍历，将最大值冒泡到末尾for(intj=0;j<n-1-i;j++){if(arr[j]>arr[j+1]){// 交换相邻元素inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}}intmain(){intarr[]={64,34,25,12,22,11,90};intn=sizeof(arr)/sizeof(arr[0]);bubbleSort(arr,n);printf("排序后的数组：\n");for(inti=0;i<n;i++){printf("%d ",arr[i]);}printf("\n");return0;}

2.3 优化技巧

可以增加一个标志位，如果某一轮没有发生任何交换，说明序列已经有序，提前结束排序：

voidbubbleSortOptimized(intarr[],intn){for(inti=0;i<n-1;i++){intswapped=0;// 标志位for(intj=0;j<n-1-i;j++){if(arr[j]>arr[j+1]){inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;swapped=1;}}// 如果没有交换，说明已有序if(swapped==0)break;}}

3. 选择排序（Selection Sort）

3.1 原理

选择排序每一轮从未排序部分选出最小值，放到已排序部分的末尾。它的交换次数比冒泡排序少，但比较次数相同。

3.2 代码实现

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;}}}

4. 插入排序（Insertion Sort）

4.1 原理

插入排序像整理扑克牌一样，将每个元素插入到前面已排序序列的正确位置。对于近乎有序的数据，插入排序效率非常高。

4.2 代码实现

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--;}arr[j+1]=key;// 插入到正确位置}}

5. 快速排序（Quick Sort）

5.1 原理

快速排序采用分治策略：选择一个基准元素（pivot），将数组分成两部分，左边都小于基准，右边都大于基准，然后递归地对两部分排序。它是实际应用中最常用的排序算法之一。

5.2 代码实现

// 分区函数：返回基准元素的最终位置intpartition(intarr[],intlow,inthigh){intpivot=arr[high];// 选择最后一个元素作为基准inti=low-1;// i 指向小于基准的区域的末尾for(intj=low;j<high;j++){if(arr[j]<pivot){i++;// 交换 arr[i] 和 arr[j]inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}// 将基准放到正确位置inttemp=arr[i+1];arr[i+1]=arr[high];arr[high]=temp;returni+1;}voidquickSort(intarr[],intlow,inthigh){if(low<high){intpi=partition(arr,low,high);quickSort(arr,low,pi-1);// 递归排序左半部分quickSort(arr,pi+1,high);// 递归排序右半部分}}

6. 归并排序（Merge Sort）

6.1 原理

归并排序同样采用分治策略：将数组不断对半拆分，直到每个子数组只有一个元素，然后两两合并成有序数组。它的时间复杂度稳定为 O(n log n)，适合大数据量排序。

6.2 代码实现

// 合并两个有序子数组voidmerge(intarr[],intleft,intmid,intright){intn1=mid-left+1;intn2=right-mid;// 创建临时数组intL[n1],R[n2];for(inti=0;i<n1;i++)L[i]=arr[left+i];for(intj=0;j<n2;j++)R[j]=arr[mid+1+j];inti=0,j=0,k=left;// 合并两个有序数组while(i<n1&&j<n2){if(L[i]<=R[j]){arr[k]=L[i];i++;}else{arr[k]=R[j];j++;}k++;}// 复制剩余元素while(i<n1){arr[k]=L[i];i++;k++;}while(j<n2){arr[k]=R[j];j++;k++;}}voidmergeSort(intarr[],intleft,intright){if(left<right){intmid=left+(right-left)/2;mergeSort(arr,left,mid);// 排序左半部分mergeSort(arr,mid+1,right);// 排序右半部分merge(arr,left,mid,right);// 合并}}

7. 排序算法对比

8. 实战：完整排序程序

下面是一个综合示例，演示如何用函数指针灵活切换不同的排序算法：

#include<stdio.h>#include<stdlib.h>// 各种排序函数声明（实现见上文）voidbubbleSort(intarr[],intn);voidselectionSort(intarr[],intn);voidinsertionSort(intarr[],intn);voidquickSort(intarr[],intlow,inthigh);voidmergeSort(intarr[],intleft,intright);// 打印数组voidprintArray(intarr[],intn){for(inti=0;i<n;i++){printf("%d ",arr[i]);}printf("\n");}intmain(){intarr[]={64,34,25,12,22,11,90};intn=sizeof(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语言中五种经典排序算法：冒泡、选择、插入、快速和归并。每种算法都有其适用场景：

• 冒泡排序：简单直观，适合教学和小规模数据
• 选择排序：交换次数少，适合交换代价高的场景
• 插入排序：对近乎有序的数据效率极高
• 快速排序：综合性能最优，实际应用最广
• 归并排序：稳定且时间复杂度有保证，适合大数据量

建议初学者先吃透冒泡和插入排序，再逐步掌握快速排序和归并排序。多动手写代码、多调试，才能真正理解每种算法的精髓。