C 语言排序算法
BB Time一、冒泡排序1、原理2、代码二、选择排序1、原理2、代码三、插入排序1、原理2、代码四、快速排序1、原理2、代码3、操作过程BB Again代码均以按从小到大排序为例
只写出来了排序的函数,减少博客冗余内容
若叙述存在差错,烦请大佬指出
BB Time
这个学期开了数据结构的课程,需要用到 C 语言,但是颓废太久感觉已经忘的差不多了。再加上有学弟(妈呀,我才上了四个月大一就已经成学长了😭)来问我排序算法,所以把之前的博客重新整理下,当作复习,也希望能帮到刚开始学 C 语言的小伙伴们。
一、冒泡排序
1、原理
通过两层循环,相邻两个数进行比较,将较大的数向后移动。第一轮循环选出最大值,第二轮选出次大值,依此类推。
因较大值不断向后移动,类似于冒泡泡,故称「冒泡排序」。
2、代码
void bubble(int a[], int n) {int i,j,t;for(i=0; i<n-1; i++) {for(j=0; j<n-1-i; j++)if(a[j] > a[j+1]) {int t = a[j];a[j] = a[j+1];a[j+1]=t;}}}
二、选择排序
1、原理
从第一个数据开始,依次选择出来与之后的数据依次比较,若小于后面的数据,则交换两者值,再继续进行比较。
以为过程中依次选择数据,故称「选择排序」。
2、代码
void select(int a[], int n) {int i,j,k;for(i = 0; i < n-1; i++) {k = i;for(j = i+1; j < n; j++)if(a[j] < a[k])k = j;if(k != i) {t = a[i];a[i] = a[k];a[k] = t;}}}
三、插入排序
1、原理
从数组中第二位开始,每次循环将待排序的元素插入到比他大的元素上一位,依次循环,直到将数据全部排序。
以为是将待排序元素插入到已排序序列中去,故称「插入排序」。
2、代码
insertsort(int *k,int n){int i,j,t;for(i=1; i<n; i++) {t = k[i];j = i - 1;while(j>=0 && k[j]>t) {k[j+1] = k[j];j--;}k[j+1] = t;}}
四、快速排序
1、原理
在待排序的数据中,取第一个数为基准值,将小于等于和大于该基准值的数据分为两组,再不断对分出的这两组分别排序(需要使用到递归算法),直到每组只剩一个数据。
快速排序相当于是冒泡排序的一个升级,将原本从一端开始的排序优化为两侧同时进行,在数据量巨大时能显著提升运行速度,故称为「快速排序」。
2、代码
void quick(int a[], int start, int end) {int l,r;l=start;r=end;a[0]=a[start];while (l<r) {while (l<r && a[r]>a[0])r—;if (l<r) {a[l]=a[r];l++;}while (l<r && a[l]<a[0])l++;if (l<r) {a[r]=a[l];r--;}}a[l]=a[0];if (start<l)quick(a, start, r-1);if (end>r)quick(a, r+1, end);}
3、操作过程
定义数组时多定义一位,将 a[0] 设置为比较的基准,在 quick 函数中定义 l 左探针和 r 右探针,分别从左到右和从右到左扫描数组,在左右探针未相遇的时候判断右探针值是否大于基准值,将小于基准的右探针和大于基准的左探针交换,将第一位基准归位,其左侧值皆小于基准,右侧均大于,对其左右分别递归,得出最终结果。
BB Again
排序作为刚开始学习 C语言过程中的重要算法,在之后可能会经常用到,所以可以把它们写成函数记在小本本上,需要的时候拿出来 cmd+C/V 就好哈哈哈。
希望能对 和去年这个时候的我一样刚开始学习计算机编程的小伙伴 提供一些帮助~
如果觉得《C语言实例——四种排序算法(冒泡排序 选择排序 插入排序 快速排序)》对你有帮助,请点赞、收藏,并留下你的观点哦!