1、冒泡排序介绍:
冒泡排序的核心思想就是:两两相邻的元素进行比较。
先用一个例子来帮助大家理解一下冒泡排序的算法是怎们进行的
有一排高矮不同的人站成一列,要按照从矮到高的顺序重新排队。
冒泡排序的方法就是,从第一个人开始,依次两两比较相邻的两个人的身高。如果左边的人比右边的高,就交换他们的位置。
这样一轮下来,最高的人就像气泡一样“浮”到了最右边。
然后再从头开始,重复刚才的比较和交换,让第二高的人“浮”到右边第二个位置。
就这样一轮一轮地比较和交换,直到所有人都排好序。
2、不使用函数的冒泡排序:
代码展示:
#include <stdio.h>
int main(){int arr[] = { 100,99,3,45,12,55,88,22,13,19 };//随机输入的数字int i = 0;int sz = sizeof arr / sizeof(arr[0]);//求数组中的元素个数for ( i = 0; i < sz - 1; i++){//总趟数int j = 0;for (j = 0; j < sz - 1 - i; j++){//一趟冒泡排序if (arr[j] > arr[j + 1]){//交换两数int k = arr[j];arr[j] = arr[j + 1];arr[j + 1] = k;}}} for (i = 0; i < sz; i++){printf("%d ", arr[i]);}//实现排序后的数组打印return 0;}
结果展示:
2.1 sz的解释:
int sz = sizeof arr / sizeof(arr[0]);
这行代码用于计算数组 arr 中的元素个数。
sizeof是 C 语言中的一个操作符,用于获取数据类型或者变量所占用的字节数。
sizeof arr 会返回整个数组所占用的字节数。
sizeof(arr[0]) 会返回数组中单个元素所占用的字节数。
然后用整个数组占用的字节数除以单个元素占用的字节数,就得到了数组中元素的个数,并将其存储在变量 sz 中。
例如,如果 arr 是一个 int 类型的数组,每个 int 类型通常占用 4 个字节。假设整个数组占用了 40 个字节,那么sz = 40 / 4 = 10 ,即数组中有 10 个元素。
这样做的好处是,即使数组的大小在不同的情况下可能会发生变化,通过这种方式计算元素个数可以提高代码的可维护性和通用性,避免了重复编码数组的大小。
2.2 i < sz - 1 和 j < sz-1-i 的解释
这里的 i 是进行冒泡排序的总趟数,sz - 1是因为对于一个含有sz个元素的数组,进行 sz - 1 趟冒泡排序就可以完成排序。
这里的 j 是进行一次冒泡排序所要交换的次数, sz-1-i 用于控制每一趟冒泡排序中比较和交换的次数。
以包含 5 个元素的数组为例:
第一趟需要比较 4 次(即 sz-1),因为要把最大的数“浮”到最后位置。
第二趟只需要比较 3 次(即 sz-1-1),因为最大的数已经在最后,不用再参与比较。
第三趟比较 2 次(即 sz-1-2)。
第四趟比较 1 次(即 sz-1-3)。
这样,每一趟比较的次数逐渐减少,通过这种方式可以在经过一定的趟数后完成整个数组的排序。
3、使用函数的冒泡排序:
#include <stdio.h>
void bublle_sort(int arr[], int sz)//实现冒泡排序
{for(int i = 0; i < sz - 1; i++)//总趟数{ //一趟冒泡排序for (int j = 0; j < sz-1-i; j++){if (arr[j] > arr [j + 1] )//相邻两数比较大小{int k = arr[j];arr[j] = arr[ j + 1];arr[j + 1] = k;}}}
}
void printf_arr(int arr[], int sz)//打印排序后的值
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}
int main()
{int arr[] = { 2,3,4,5,6,7,1,8,9,10 };//这里的整数是可以任意输入的,不限数量//写一个函数,实现冒泡排序//假设为升序排列int sz = sizeof arr / sizeof(arr[0]);//求数组中元素的个数bublle_sort(arr, sz);//实现冒泡排序printf_arr(arr, sz);//实现打印排序后的值return 0;
}
这里就比上面那个多了两个函数,里面注释写的还是比较清楚的,可以看一看
4、关于函数冒泡排序的代码改进
void bublle_sort(int arr[], int sz)//实现冒泡排序
{for(int i = 0; i < sz - 1; i++)//总趟数{ //一趟冒泡排序for (int j = 0; j < sz-1-i; j++){if (arr[j] > arr [j + 1] )//相邻两数比较大小{int k = arr[j];arr[j] = arr[ j + 1];arr[j + 1] = k;}}}
}
关于冒泡排序的次数,上述这组代码不管所给的数字是什么顺序排列的,想要改为升序都需要进行45组两数相比,如果所要排序的数组是乱序的话45次还能接受,但是如果所给的顺序是
9 0 1 2 3 4 5 6 7 8
像上述这种顺序改为升序仅仅只需要将9移动到最后一位即可,也就是说只需要一趟冒泡排序即可完成。但是,向上面的代码,当第一趟冒泡排序结束后,会紧接着进行下一趟冒泡排序。虽然排序已经完成,但是后面依旧会继续比较,虽然数字不会再交换顺序。因此,向这种情况我们应该怎么改进呢?
#include <stdio.h>
void bublle_sort(int arr[], int sz)
{
for(int i = 0; i < sz - 1; i++)//总趟数
{ //一趟冒泡排序
int flag = 1;//假设已经有序了
for (int j = 0; j < sz-1-i; j++)
{
if (arr[j] > arr [j + 1] )
{
int k = arr[j];
arr[j] = arr[ j + 1];
arr[j + 1] = k;
flag = 0;//说明其中发生了交换,假设不成立
}
}
if (flag == 1)//说明假设成立
{
break;//跳出循环
}
}
}
看上面被标红的代码,当我们这样优化后,可以减少多余的循环,提高效率。
5、使用指针的冒泡排序:
先补充几个知识点:
数组的数组名arr就是首元素地址,所以我们传参传的其实就是首元素地址bublle_sort(arr, sz);
我们将形参改写为指针,通过指针找回来的还是main函数里的原数组
主函数里的数组传递给冒泡排序函数,冒泡函数里使用的数组依然是主函数里的数组,这是因为数组传参传的是它的地址。
使用指针标识的冒泡函数
#include <stdio.h>
void bublle_sort(int* arr, int sz)//实现冒泡排序
{for (int i = 0; i < sz - 1; i++)//总趟数{ //一趟冒泡排序int flag = 1;for (int j = 0; j < sz - 1 - i; j++){if (*(arr + j) > *(arr + j + 1))//相邻两数比较大小{int k = *(arr+j);*(arr + j) = *(arr + j + 1);*(arr + j + 1) = k;flag = 0;}}if (flag == 1){break;}}
}
void printf_arr(int* arr, int sz)//打印排序后的值
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", *(arr + i));}printf("\n");
}
int main()
{int arr[] = { 2,3,4,5,6,7,1,8,9,10 };//写一个函数,实现冒泡排序//假设为升序排列int sz = sizeof arr / sizeof(arr[0]);bublle_sort(arr, sz);//实现冒泡排序printf_arr(arr, sz);//实现打印排序后的值return 0;
}
结语:
本篇文章到这里就先结束了,期待大家的的阅读!!!