草庐IT

经典算法冒泡排序之标志位优化版

微凉秋意 2023-04-12 原文

活动地址：CSDN21天学习挑战赛

✅作者简介：C/C++领域新星创作者，为C++和java奋斗中
✨个人社区：微凉秋意社区
🔥系列专栏：经典算法
📃推荐一款模拟面试、刷题神器👉注册免费刷题

🔥前言

今天总结一下优化版的经典算法——冒泡排序，不同于以往的暴力二重for循环，这里的冒泡排序增加了一个标志位。我们要理解该冒泡排序的概念，算法流程与算法思想，探讨时间复杂度。这也是本专栏第六篇博文，感兴趣的朋友可以订阅以便持续观看。

文章目录

冒泡排序算法解析

一、理解冒泡排序思想

1、算法概念

也称气泡排序，是经典的交换排序方法。整个过程就是在无序区中对相邻元素进行两两比较，将不满足相对顺序的一对儿元素进行交换，再进行下一对元素的比较。

2、算法思想

总结来说，每一趟冒泡排序将会排好一个元素(极值)。不断的在无序区中执行该步骤，如果在某一次比较的过程中没有发生元素的交换，则证明元素都已经有序，可以提前结束整个算法。或者直到无序区中的元素减少到一个时，整个算法结束，此时整个序列有序。

二、算法分析

1、算法流程

假如要对该序列进行冒泡排序，解析一下算法流程：

  1. 第一趟排序：7和4 交换位置，变为：
  2. 第二趟排序：6和4 交换位置，变为：
  3. 此时序列符合升序排列，提前结束循环，排序完成，退出循环

2、实现步骤

  1. 首先当外层循环 i 为0时，内层循环中从序列里第一个元素开始两两计较，不是升序则交换位置，是升序则往后遍历，那么第一次外层循环一定可以确定最大值且位置在序列末尾。
  2. 那么当外层循环次数增多，内层循环范围就要对应缩减，应为总长度 - 外层循环次数 - 1(减1是为了防止 i 等于0时数组溢出)。
  3. 重复以上步骤，如果序列已经为升序，通过标志位来提前结束程序。

三、代码实现

1、源码及运行效果

C++源代码：

#include<iostream>
using namespace std;
//冒泡排序声明
void maopaosort(int A[], int len);
//冒泡排序实现
void maopaosort(int A[], int len)
{
	for (int i = 0; i < len; i++) {
		int flag = 0;//标志位
		for (int j = i; j < len - i - 1; j++) {
			if (A[j] > A[j + 1]) {
				int temp = A[j];
				A[j] = A[j + 1];
				A[j + 1] = temp;
				flag = 1;
			}
		}
		if (flag == 0)//如果已经升序，不再继续外层循环，结束此函数
			return;
	}
	return ;
}
int main(void)
{
	int A[7] = { 3,6,7,4,8,9,10 };
	int len = sizeof(A) / sizeof(A[0]);
	cout << "排序前：" << endl;
	for (int i = 0; i < len; i++) {
		cout << A[i] << " ";
	}
	maopaosort(A,len);
	cout << "排序后：" << endl;
	for (int i = 0; i < len; i++) {
		cout << A[i] << " ";
	}
}

运行效果：

2、时间复杂度分析

  1. 最好的情况：
    • 该序列为升序排列，内层循环执行了n-1次，那么相当于遍历了n次，时间复杂度为O(n)。
  2. 最坏的情况：
    • 对于冒泡排序来说，最坏的情况依然是元素逆向有序，此时需要执行n-1趟，并且两两元素都需要交换，相当于是最小的元素排在末尾，—路交换到第一位，然后是次最小一路交换至第二位，此时的时间复杂度为: O( n 2 n^2 n2)。
  3. 平均情况：
    • 综合考虑下，冒泡排序算法的时间复杂度为O( n 2 n^2 n2)。

那么有关优化版冒泡排序算法的分析到此结束了，快去敲一波代码试试效果吧！最后期待你的关注与支持，让我们共同进步！
​

经典算法quotspanlt

有关经典算法冒泡排序之标志位优化版的更多相关文章

  1. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  2. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

    嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

  3. Hive SQL 五大经典面试题 - 2

    目录第1题连续问题分析：解法：第2题分组问题分析：解法：第3题间隔连续问题分析：解法：第4题打折日期交叉问题分析：解法：第5题同时在线问题分析：解法：第1题连续问题如下数据为蚂蚁森林中用户领取的减少碳排放量iddtlowcarbon10012021-12-1212310022021-12-124510012021-12-134310012021-12-134510012021-12-132310022021-12-144510012021-12-1423010022021-12-154510012021-12-1523.......找出连续3天及以上减少碳排放量在100以上的用户分析：遇到这类

  4. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  5. ruby-on-rails - 在具有 ActiveRecord 条件的相关模型中按字段排序 - 2

    我正在尝试按Rails相关模型中的字段进行排序。我研究的所有解决方案都没有解决如果相关模型被另一个参数过滤？元素模型classItem相关模型:classPriority我正在使用where子句检索项目:@items=Item.where('company_id=?andapproved=?',@company.id,true).all我需要按相关表格中的“位置”列进行排序。问题在于，在优先级模型中，一个项目可能会被多家公司列出。因此，这些职位取决于他们拥有的company_id。当我显示项目时，它是针对一个公司的，按公司内的职位排序。完成此任务的正确方法是什么？感谢您的帮助。PS-我

  6. ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2

    我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby​​做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排

  7. ruby-on-rails - 在不重新查询数据库的情况下重新排序 Rails 中的事件记录？ - 2

    例如，假设我有一个名为Products的模型，并且在ProductsController中，我有以下代码用于product_listView以显示已排序的产品。@products=Product.order(params[:order_by])让我们想象一下，在product_listView中，用户可以使用下拉菜单按价格、评级、重量等进行排序。数据库中的产品不会经常更改。我很难理解的是，每次用户选择新的order_by过滤器时，rails是否必须查询，或者rails是否能够以某种方式缓存事件记录以在服务器端重新排序？有没有一种方法可以编写它，以便在用户排序时rails不会重新查询结果

  8. ruby - 从 Ruby 中的国家代码获取表情符号标志 - 2

    我想将“US”之类的国家代码转换为表情符号标志，即将“US”字符串转换为Ruby中适当的Unicode。Here'sanequivalentexampleforJava 最佳答案 使用tr将字母字符转换为其区域指示符号:'US'.tr('A-Z',"\u{1F1E6}-\u{1F1FF}")#=>"??"当然你也可以直接使用Unicode字符:'US'.tr('A-Z','?-?')#=>"??" 关于ruby-从Ruby中的国家代码获取表情符号标志，我们在StackOverflow上找

  9. ruby-on-rails - 如何对对象数组进行排序？ - 2

    我有一个对象如下:[{:id=>2,:fname=>"Ron",:lname=>"XXXXX",:photo=>"XXX"},{:id=>3,:fname=>"Dain",:lname=>"XXXX",:photo=>"XXXXXXX"},{:id=>1,:fname=>"Bob",:lname=>"XXXXXX",:photo=>"XXXX"}]我想按fname排序，不区分大小写，所以它会导致编号:1,3,2我该如何排序？我正在尝试:@people.sort!{|x,y|y[:fname]x[:fname]}但这没有任何效果。 最佳答案

  10. ruby - 使用自定义排序首选项对数组进行排序？ - 2

    有人可以告诉我如何根据自定义字符串对嵌套数组进行排序吗？比如有没有办法排序:[['Red','Blue'],['Green','Orange'],['Purple','Yellow']]“橙色”、“黄色”，然后是“蓝色”？最终结果如下所示:[['Green','Orange'],['Purple','Yellow'],['Red','Blue']]它不是按字母顺序排序的。我很想知道我是否可以定义要排序的值以实现上述目标。 最佳答案 sort_by对于这种排序总是非常方便:a=[['Red','Blue'],['Green','Ora

随机推荐