入门基础：四大基础排序算法（C语言实现）

四大基础排序算法

排序算法是编程世界的基石，本文深入讲解四种最基础、最常用的排序算法：冒泡排序、快速排序、插入排序和选择排序。

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

常见错误总结：

1. 数组越界：必须确保内层循环条件是j<len-1-i
2. 忘记使用临时变量：直接交换会导致数据丢失

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);// 右半部分}}

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

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