草庐IT

C++常见排序算法——冒泡排序算法

冷漩 2024-05-04 原文

首先说一下冒泡排序的基本算法思想：

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

以从小到大排序为例：a[5]={3,5,4,1,0};

  1. 先将3和5进行比较，已经是我们需要的正序，不需要交换位置；
  2. 再将5和4进行比较，不是正序，相互交换顺序，序列变为{3,4,5,1,0}。
  3. 再将5和1进行比较，不是正序，相互交换顺序，序列变为{3,4,1,5,0}。
  4. 再将5和0进行比较，不是正序，相互交换顺序，序列变为{3,4,1,0,5}。

至此，第1轮冒泡就已经完成了，最大值5到了序列的最后面。

由于5的位置已经排好序，所以第2轮，5不再参与排序，将{3,4,1,0}置为有序序列即可。

假设数组元素个数为n，从上面第1轮的比较来看，我们可以得出如下结论：

  1. 我们将冒泡排序的轮数设为 i ，每完成1轮冒泡排序，就会增加一个元素处于有序状态，所以在 (n-1) 轮排序结束后，就会有 n-1 个元素处于有序状态，而剩下的最后一个元素，自然是最小（大）值，不用再进行排序，所以，冒泡排序比较的轮数为 (n-1) 。
  2. 我们将每轮需要比较的次数设为 j ，第1轮( i 值为0)需要比较的次数为4，从 {3,4,1,0} 中不难看出，第2轮( i 值为1)需要比较的次数为3次，说明每轮比较的次数 j 与冒泡的轮数  i  值有关，且 j = n-i-1。

确定好上面两条结论以后，我们开始用代码实现冒泡排序算法：

#include <iostream>
using namespace std;
//对a[]进行正序(从小到大)排序
void bubblesort(int *a,int len)	//形参a取到实参a传递过来的数组首地址
                                //然后解引用，取到数组的值 
{
	for (int i=0;i<len-1;i++)	//i控制排序的轮数 
	{
		for (int j=0;j<len-i-1;j++)	//j控制每轮需要比较的次数 
		{
			if(a[j+1]<a[j])	//不满足正序要求，交换顺序 
			{
				int temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}	
}

int main()
{
	int a[10]={2,6,3,8,5,1,0,7,9,4};
	int len = sizeof(a)/sizeof(int);	//	计算数组元素个数 
	bubblesort(a,len);	//a为数组a[10]首地址，作为实参传递给形参 
	for(int i=0;i<len;i++)
	{
		cout<<a[i]<<" ";
	}
	return 0;
}

得到正序排列的值： 0 1 2 3 4 5 6 7 8 9。

 

C++mdashxff0cxffxff0数据结构排序算法

有关C++常见排序算法——冒泡排序算法的更多相关文章

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

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

  2. git使用常见问题（提交代码，合并冲突） - 2

    文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g

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

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

  4. ruby - 将对象设置为 nil 是否很常见？ - 2

    我正在构建一个应用程序，想知道是否将未使用的对象设置为nil是生产级编码中的常见做法。我知道这只是垃圾收集器的提示，并不总是处理对象。 最佳答案 根据这个thread如果您使用完一个成员对象，将其设置为nil将引发被引用对象被垃圾回收。如果它是局部变量，方法exit将做同样的事情。也就是说，如果您要求将成员显式设置为nil，我会质疑您的设计。 关于ruby-将对象设置为nil是否很常见？，我们在StackOverflow上找到一个类似的问题： https://

  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 - 变量赋值后的 if 语句 - 有多常见？ - 2

    我最近与一位同事讨论了以下Ruby语法:value=ifa==0"foo"elsifa>42"bar"else"fizz"end我个人并没有看到太多这种逻辑，但我的同事指出，这实际上是一种相当普遍的Rubyism。我试着用谷歌搜索这个主题，但没有找到任何文章、页面或SO问题来讨论它，这让我相信这可能是一种非常实际的技术。然而，另一位同事发现语法令人困惑，而是将上面的逻辑写成这样:ifa==0value="foo"elsifa>42value="bar"elsevalue="fizz"end缺点是value=的重复声明和隐式elsenil的丢失，如果我们想使用它的话。这也感觉它与Ruby

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

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

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

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

  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

随机推荐