基础算法之冒泡排序(bubble sort)
2021/5/12 22:27:11
本文主要是介绍基础算法之冒泡排序(bubble sort),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
0,(注)
由于冒泡排序也分为升序(asc)和降序(desc)排列,为了防止过多的代码,因此我们次文只选择升序作为展示,完整的优化降序代码也将会在文章尾部(Example1)贴出来。那么接下来我们一起来进入可爱的冒泡算法吧!
1,算法名称:升序冒泡排序(ascending bubble sort)
2,时间复杂度:O(n^2)
3,实现方式:C语言
4,空间复杂度:O(1)
5,稳定性:稳定
6,算法思想:
.比较相邻的元素。如果第一个比第二个大,就交换它们两个;
.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数;
.针对所有的元素重复以上的步骤,除了最后一个;
.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
7,算法实现
在实现算法中,我们会首先从最简单的一板开始,然后分析其中的不足,最后在贴出它的优化后的算法。
7.1 基础版的算法代码
#include<stdio.h> #include<stdlib.h> /* 交换函数 */ swap(int *a,int *b){ int temp; temp = *a; *a = *b; *b = temp; } /* 升序冒泡 */ void bubblesortAsc(int *a,int len) { int i,j; for(i = 0; i < len-1; i++){ /*每排序一趟,则至少有一个元素已经有序,用 j<len-i-1 可以缩小排序范围 */ for(j = 0; j < len-1-i;j++){ if(a[j] > a[j+1]){ swap(&a[j],&a[j+1]); } } } } int main() { int num[5]={3,1,5,6,2}; int i=0; bubblesortAsc(num,5); for(i=0;i<5;i++) { printf("%d ",num[i]); } return 0; }
存在问题:可以看出,整体的排序过程比较繁琐,主要是因为要进行两次的循环,并且循环的次数全为N,有一种情况,那就是未排序的序列如果已经是有序排列了,那么算法就要执行好多多余的步骤,就上边的代码实现,假如现在:
int num[5] = {6,1,2,3,5};
我们可以直观的观察出,此代码只要执行一次外部循环就可以成为有序序列,但是由于我们没有及时的中断它的操作,因此造成了许多不必要的比较。
优化方法:对函数加一个flag标识,假如一次的循环中没有发生swap(),那么我们就比较flag的值,执行跳出函数操作!具体情况参见代码。
7.2 优化版的算法代码
#include<stdio.h> #include<stdlib.h> /* 交换函数 */ swap(int *a,int *b){ int temp; temp = *a; *a = *b; *b = temp; } /* 升序冒泡 */ void bubblesortAsc(int *a,int len) { int i,j; bool flag; //没有交换的标记 for(i = 0; i < len-1; i++){ flag = 0; /*每排序一趟,则至少有一个元素已经有序,用 j<len-i-1 可以缩小排序范围 */ for(j = 0; j < len-1-i;j++){ if(a[j] > a[j+1]){ swap(&a[j],&a[j+1]); flag = 1; } } if(!flag) break; } } int main() { int num[5]={3,1,5,6,2}; int i=0; bubblesortAsc(num,5); for(i=0;i<5;i++) { printf("%d ",num[i]); } return 0; }
---------------------------END--------------------------------
Example 1
#include<stdio.h> #include<stdlib.h> /* 交换函数 */ swap(int *a,int *b){ int temp; temp = *a; *a = *b; *b = temp; } /* 降序冒泡 */ void bubblesortAsc(int *a,int len) { int i,j; bool flag; //没有交换的标记 for(i = 0; i < len-1; i++){ flag = 0; /*每排序一趟,则至少有一个元素已经有序,用 j<len-i-1 可以缩小排序范围 */ for(j = 0; j < len-1-i;j++){ if(a[j] < a[j+1]){ swap(&a[j],&a[j+1]); flag = 1; } } if(!flag) break; } } int main() { int num[5]={3,1,5,6,2}; int i=0; bubblesortAsc(num,5); for(i=0;i<5;i++) { printf("%d ",num[i]); } return 0; }
其实就是把其中的“>”"<"号发生了更改。
参考:冒泡排序算法及其优化
基础算法总结
这篇关于基础算法之冒泡排序(bubble sort)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南