【C语言】冒泡排序
慕雪年华

冒泡排序

@[TOC]

无内鬼,直入主题!

冒泡排序的思想核心是:比较两两相邻的元素,并且可能的话需要交换

说人话就是

把原本是9,8,7,6,5,4,3,2,1,0的数组

变成0 ,1,2,3,4,5,6,7,8,9

也可以把无序的数组排列为有序(从小到大or从大到小)

基本的流程如下图:

image

同时我们可以计算出,0·9这十个数字,重新排列完需要循环9次

也就是N个数字需要N-1趟的排列

代码实现

说完了原理,还是需要敲代码来实现

“老铁们int main return 0走一波!”

1
2
3
4
5
6
7
8
#include<stdio.h>
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };//排序为升序 - 冒泡排序
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz);//冒泡排序的自定义函数
return 0;
}
  • 一维数组[]中的元素个数可以省略

SZ的位置问题

这里必须要注意的一点是

sizeof必须在主函数中计算元素个数

因为如果在自定义函数中计算的话

1
2
3
4
5
void bubble_sort(int arr[])
{
int sz = sizeof(arr) / sizeof(arr[0]);//放在此处sz计算为1,err
for (i = 0; i < sz; i++)
}

SZ计算出来的结果是1

  • arr数组名,传送的是数组首元素的地址
  • arr作为形参,无法计算内部元素个数
  • 对后续要进行的操作如for循环中的 i<sz来说自定义函数中计算的sz是无效的

更具体的原因在上一篇博客《什么是数组名?》中有介绍

排除此问题后,sz计算出的元素个数就是我们的N

这里以i为趟数,i<sz指趟数需小于元素个数

1
2
3
4
5
6
7
8
9
void bubble_sort(int arr[], int sz)//形参arr本质是指针
{
//确定趟数
int i = 0;
for (i = 0; i < sz; i++)
{
//
}
}

接着书写第二环的for循环,即每一趟冒泡排序的操作

1
2
3
4
5
6
7
8
9
       //一趟冒泡排序
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1] )
{
//
}
}

这里需要注意的是j与sz的大小关系

按照前面的流程图,每运行一趟冒泡序列,就会有一个数字被移动到数组的最后面

N个元素需要进行N-1次冒泡排序,同时经过一趟后,新的最后一个元素无需重新比对排序

所以 j<sz-1-i

比较&交换

因为int arr传入的是指针变量,如果想要自定义函数影响函数外的内容,也必须使用指针变量

1
2
3
4
          //交换
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;

实际进行两个数字之间的比较和交换的是上述代码

tmp这个空盒子也是我们的老朋友了

总结起来完整的自定义函数如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void bubble_sort(int arr[], int sz)//因为在主函数中计算sz,这里需要加上int sz
{
//确定趟数
int i = 0;
for (i = 0; i < sz; i++)
{
//一趟冒泡排序
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1] )
{
//交换
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}

接下来我们可以用F10的监视器查看代码运行情况

image

arr数组初始化完成,sz计算得出为10

继续进行下一步,arr数组中的内容成功被排列

image

冒泡排序完成!

结语

冒泡排序是对循环语句、自定义函数、下标以及数组的综合运用

了解它的原理有助于我们写出更为复杂的排列组合代码

点个赞再走呗,谢谢了!