九大排序算法（c语言版）

过年这几天晚上在家码代码学了一点。

代码中排序的数字均由rand()函数随机生成。

一、冒泡排序（2.8）

一个经典的不能再经典的排序算法。

优化前：

#include#include#include#define N 100void intiArr(int arr[],int length){for(int i=0;i<length;i++)arr[i]=rand()%N;}void showArr(int arr[],int length){for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n------------------\n");}void bubleSort(int arr[],int length){for(int i=0;i<length-1;i++){for(int j=0;j<length-1-i;j++){if(arr[j+1]

两个for循环搞定。

优化后：

#include#include#include#define MAXSIZE 20void intiArr(int arr[],int length){for(int i;i<length;i++){arr[i]=rand()%20;}}void showArr(int arr[],int length){for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n---------------------\n");}bubSort(int arr[],int length){int flag=1;while(length--&flag){flag=0;for(int i=0;i<length;i++){if(arr[i+1]

加入了一个flag变量，用于减少多余的比较和交换，大大提高代码运行效率，减少循环次数。

二、插入排序（2.9）

#include#include#include#define MAXSIZE 20void intiArr(int arr[],int length){for(int i=0;i<length;i++){arr[i]=rand()%20;}}void showArr(int arr[],int length){for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n-----------------\n");}void insertSort(int arr[],int length){for(int i=1;i=1&&arr[j]

冒泡增强版，就是拿后面的数字和前面的相比，小的放前面。

三、选择排序（2.10）

#include#include#include#define MAXSIZE 20void initArr(int arr[],int length){for(int i=0;i<length;i++){arr[i]=rand()%20;}}void showArr(int arr[],int length){for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n-----------------\n");}void selectSort(int arr[],int length){for(int i=0;i<length;i++){int k=i;for(int j=i+1;j<length;j++){if(arr[j]

需要定义i,j,k三个变量，i,k从0出发,j从1出发，j往后排查有没有比i更小的数字，然后寄存在k里，经过这一轮循环，i与k交换位置，i++。

四、希尔排序（2.11）

#include#include#include#define MAXSIZE 20void intiArr(int arr[],int length){for(int i=0;i<length;i++){arr[i]=rand()%20;}}void showArr(int arr[],int length){for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n-----------------\n");}void shellArr(int arr[],int length){int h=1;int t=length/3;while(h=1){for(int i=h;i=h&&arr[j]

设置步长为h，数字之间跨越比较，有点类似那个约瑟夫环，处理起多的数据比插入排序要好。

五、快速排序（2.12）

快速排序是我个人认为这9个排序算法里面最好用的，快速排序之所以是里面唯一一个名字里面敢称快速的，说明发明它的人还是很自信的，它的逻辑不难，处理效率也极高。

#include#include#include#define MAXSIZE 20void intiArr(int arr[],int length){for(int i=0;i<length;i++){arr[i]=rand()%20;}}void showArr(int arr[],int length){for(int i=0;i=right)return;int i=left;int j=right;int pivot=arr[i];while(i<j){while(i=pivot){j--;}arr[i]=arr[j];while(i<j&&arr[i]<=pivot){i++;}arr[j]=arr[i];}arr[i]=pivot;quickSort(arr,left,i-1);quickSort(arr,i+1,right);}int main(){srand((unsigned int)time(NULL));int arr[MAXSIZE];intiArr(arr,MAXSIZE);showArr(arr,MAXSIZE);quickSort(arr,0,MAXSIZE-1);showArr(arr,MAXSIZE);system("pause");}

中间设置一个轴pivot,让左右两边的数和轴进行比较，确保轴的左边都小于轴，轴的右边都大于轴；找到中位数之后进行递归，函数自己调用自己，向左向右递归扫清那些无序的数。

六、归并排序（2.13）

优化前：

#include#include#include#define MAXSIZE 20void intiArr(int arr[],int length){for(int i;i<length;i++){arr[i]=rand()%20;}}void showArr(int arr[],int length){for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n---------------------\n");}void mergeSort(int a[],int alen,int b[],int blen,int* temp){int i=0;int j=0;int k=0;while(i

优化前只能对两组已经排好序的短数组进行重新排序然后合并，遍历a，b数组然后进行相互比较，数值小的那个赋值到temp数组里面，如果a，b数组长度不一样，其中一个遍历完之后，那另一数组中剩余的数字直接赋值进temp数组中，这样合并后的temp数组就是一个有序的长数组。

优化后：

#include#include#include#include#define MAXSIZE 20void initArr(int arr[],int length){for(int i=0;i<MAXSIZE;i++){arr[i]=rand()%20;}}void showArr(int arr[],int length){for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n-----------------\n");}void merge(int arr[],int low,int mid,int height,int *temp){int i=low;int j=mid+1;int k=low;while(i<=mid&&j<=height)temp[k++]=arr[i]=height)return;int mid=low+(height-low)/2;merge_sort(arr,low,mid,temp);merge_sort(arr,mid+1,height,temp);merge(arr,low,mid,height,temp);}void mergeSort(int arr[],int length){int *temp=(int *)malloc(sizeof(int)*length);assert(temp);merge_sort(arr,0,length-1,temp);free(temp);}int main(void){srand((unsigned int)time(NULL));int arr[MAXSIZE];initArr(arr,MAXSIZE);showArr(arr,MAXSIZE);mergeSort(arr,MAXSIZE);showArr(arr,MAXSIZE);system("pause");return 0;}

优化过后的算法相比之前复杂了挺多，但是应用范围更广了，可以处理那些不是有序的数组，需要先定义三个变量，先用第二个函数分隔，然后用第一个函数对前中后进行分部处理，注意mid通过low和height定义时，需要定义成

int mid=low+(height-low)/2;

而不能定义为

int mid=(low+height)/2;

因为考虑到越界的问题。

另外这个算法也需要递归和调用其他的函数，先分部再进行比较，不过写完之后使用起来很方便，还是只需要传入一个数组和它的长度作为参数就能实现，逻辑上和优化前的归并排序还是比较相似的，还是进行拆分与合并。

七、堆排序（2.14）

太难了，还没学会〒▽〒

情人节被堆排序干爆了，分外堆和内堆，下次搞懂了再专门写一篇文章细细讲解。

八、计数排序（2.15）

#include#include#include#define MAXSIZE 20#define N 100void intiArr(int arr[],int length){for(int i=0;i<length;i++)arr[i]=rand()%100;}void showArr(int arr[],int length){for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n----------------\n");}int temp[N];void countSort(int arr[],int length){for(int i=0;i<length;i++){temp[arr[i]]++;}for(int i=0,j=0;i<N;i++){while(temp[i]--)arr[j++]=i;}}int main(void){srand((unsigned int)time(NULL));int arr[MAXSIZE];intiArr(arr,MAXSIZE);showArr(arr,MAXSIZE);countSort(arr,MAXSIZE);showArr(arr,MAXSIZE);system("pause");}

这个逻辑也比较简单，就是先统计数据里面都有哪些数，给这些数量非0的数分别开辟几片内存空间，然后从小到大依次按量释放。

九、基数排序（2.16）

#include#include#include#define MAXSIZE 100#define N 1000void intiArr(int arr[],int length){for(int i=0;i<length;i++){arr[i]=rand()%N;}}void showArr(int arr[],int length){for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n----------------\n");}int Temp[10][N];void radixSort(int arr[],int length){int i,j;int pos;for(int k=10;k<10000;k*=10){for(i=0;i<length;i++){j=0;pos=(arr[i]%k)/(k/10);while(Temp[pos][j])j++;Temp[pos][j]=arr[i];}pos=0;for(i=0;i<10;i++){for(j=0;j<length&&Temp[i][j]!=0;j++){arr[pos++]=Temp[i][j];Temp[i][j]=0;}}}}int main(){srand((unsigned int)time(NULL));int arr[MAXSIZE];intiArr(arr,MAXSIZE);showArr(arr,MAXSIZE);radixSort(arr,MAXSIZE);showArr(arr,MAXSIZE);system("pause");}

举个例子：对以下序列进行基数排序
578，234，86，432，512，618，384
排序过程：
第一轮（在第零轮的基础上按位排在第零轮的基础上按位排在第零轮的基础上按10的零次方位排）：432，512，234，384，86，578，618
第二轮（在第一轮的基础上按位排在第一轮的基础上按位排在第一轮的基础上按10的一次方位排）：512，618，432，234，578，384，86
第三轮（在第二轮的基础上按位排在第二轮的基础上按位排在第二轮的基础上按10的二次方位排）：86，234，384，432，512，578，618
第三轮结束序列自然排好序。86不够3位数，就往前面补零，即86 = 086.

最后安利一下这个宝藏up主，我是跟着他学的，他应该现在也是个大学生，讲的还是比较细的。

【十大经典排序算法（C语言描述）】https://www.bilibili.com/video/BV1nN4y1M7JK?p=10&vd_source=f0b5cc5a36c7293744b45f51763cd943

这是本人在寒假发布的第二篇文章，希望里面的一些代码能对你有一点点的帮助，我们一起进步。

不要欺负萌新哦~

​​​​​​​​​​​​​​​​​​​​​