200字范文 > C语言实例——四种排序算法（冒泡排序选择排序插入排序快速排序）

C语言实例——四种排序算法（冒泡排序选择排序插入排序快速排序）

时间：2018-09-03 19:33:05

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 右探针，分别从左到右和从右到左扫描数组，在左右探针未相遇的时候判断右探针值是否大于基准值，将小于基准的右探针和大于基准的左探针交换，将第一位基准归位，其左侧值皆小于基准，右侧均大于，对其左右分别递归，得出最终结果。