草庐IT

排序算法之详解冒泡排序

发着呆看星的博客 2023-12-12 原文

引入

  • 冒泡排序顾名思义，就是像冒泡一样，泡泡在水里慢慢升上来，由小变大。
  • 虽然冒泡排序和冒泡并不完全一样，但却可以帮助我们理解冒泡排序。

思路

  • 一组无序的数组，要求我们从小到大排列
    1. 我们可以先将最大的元素放在数组末尾
    2. 再将第二大的数放在数组的倒数第二个位置
    3. 再将第三大的数放在数组的倒数第三个位置
    4. 以此类推
  • 那么现在问题的关键就是如何将 第 n 大的数 放在 倒数第 n 个位置 ---> 交换
  • 下面是冒泡排序的gif动画，该图来自于菜鸟教程

实现

提醒

  • 现在我们假设无序数组长度为 n 即下标 [ 0 , n-1 ]
  • 当前元素下标为 i ，下一个元素的下标为 j

第一次遍历 [ 0 , n - 1- 1 ] ---> [ 0 , n -2 ]

  • 如果 当前元素 > 后一个元素 ，那么就交换两个元素 ， 再进行下次遍历
  • 如果 当前元素 > 后一个元素 , 直接进行下次遍历
  • 直到遍历完成之后，最大的值就在一次一次的交换中被交换到了数组末尾
  • 思考：为什么是从 0 开始遍历 ，n-2 结束 ?
    1. 因为 j 为 i 的下一个元素下标 ，如果为 [ 0，n-1 ]的话 ，那么当前元素下标就可以为 n - 1，那么下一个元素的下标就为 n ，显然数组下标越界了
    2. 而且正因为是从 [ 0 , n -2] 范围遍历 ，刚好可以保证经过这一轮遍历后 ，最大的数在数组末尾 ( i = n - 2 【即为倒数第二个数】 ，j = i + 1【末尾数】)

第二次遍历 [ 0 , n - 1- 2]----> [ 0 , n -3 ]

  • 经过第一次遍历，我们已经将最大的数移动到了数组末尾，所以，我们不用在去对末尾以确定的数进行比较，我们可以减少次数，来提高效率
  • 再次引用第一次遍历的步骤

......
最后一次遍历 [ 0 , n - 1 - (n-1) ] ---- > [ 0 , 0 ]

  • 最后一次遍历的情况就是还剩下两个元素未进行排序的情况 ，即下标 0 和 下标 1 未进行排序
  • 只需对这两个元素进行排序后，就完成了这个数组的排序

怎么确定一共需要遍历几次及每次遍历的数组下标范围

  • 遍历次数问题
    • 我们先来做一个假设
      • 如果一个数组只有两个元素，那么应该遍历几次 ? 1 次
      • 如果一个数组只有三个元素，那么应该遍历几次 ? 2次
        • 第一次将最大的数放在最末尾 ，第二次将第二大的数放在倒数第二 ， 第三大的元素自然而然就在倒数第三了【即第一个】 ，不用遍历
      • 如果一个数组只有四个元素，那么应该遍历几次 ? 3 次
        • 第一次将最大的数放在最末尾 ，第二次将第二大的数放在倒数第二 ， 第三次将第三大的元素放在在倒数第三 ，剩下一个元素，不用排
      • 显而易见，如果有 n 个 元素 ，那么就需要遍历 n - 1 次
  • 每次遍历数组下标
    • 按照上面的实现部分
      • 第一次遍历我们需要数组的下标为 [ 0 , n -2 ]
      • 第二次遍历我们需要数组的下标为 [ 0 , n -3 ]
      • 第三次遍历我们需要数组的下标为 [ 0 , n -4 ]
    • 那么就有一个规律了 ，n - 2 ， n - 3 ， n - 4
      • 当我们正在进行第一次遍历时，用一个变量保存 m = 1 ， 那么第一次遍历下标可以为 [ 0 , n -1 - m ]
      • 当我们正在进行第二次遍历时，用一个变量保存 m = 2 ， 那么第一次遍历下标可以为 [ 0 , n -1 - m ]
      • 当我们正在进行第三次遍历时，用一个变量保存 m = 3 ， 那么第一次遍历下标可以为 [ 0 , n -1 - m ]
      • 当我们正在进行最后一次遍历时，用一个变量保存 m = n - 1， 那么第一次遍历下标可以为 [ 0 , n -1 - m ] ---> [ 0 , n - 1 - (n -1) ]

代码实现

// 冒泡排序算法
public static int[] bubble(int[] ints){
    // 注意我这里使用的是 <  ， 而不是我思路中的  <= , 可以自行更改 ，如果没想明白说明你还没有理解
    // 用 i 来表示一共需要遍历多少次
    for (int i = 0; i < ints.length-1; i++) {
        // 真正开始进行遍历 ，根据 i 的值 不同 ，j 就不同 ，也就是说每次大遍历中小遍历的次数不同
        for (int j = 0; j < ints.length-1-i; j++) {
            // 如果前一个元素 >  后一个元素 ，则交换
            if (ints[j] > ints[j+1]){
                int temp = ints[j];
                ints[j] = ints[j+1];
                ints[j+1] = temp;
            }
            // 继续下次遍历
        }
    }
    return ints;
}
详解排序liblockquotestrong算法与数据结构

有关排序算法之详解冒泡排序的更多相关文章

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

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

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

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

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

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

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

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

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

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

  6. 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]}但这没有任何效果。 最佳答案

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

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

  8. Ruby 将对象插入现有的已排序对象数组 - 2

    我有以下现有的Dog对象数组，它们按age属性排序:classDogattr_accessor:agedefinitialize(age)@age=ageendenddogs=[Dog.new(1),Dog.new(4),Dog.new(10)]我现在想插入一条新的狗记录，并将它放在数组中的正确位置。假设我想插入这个对象:another_dog=Dog.new(8)我想把它插入到数组中，让它成为数组中的第三项。这是一个人为的示例，旨在演示我特别想如何将一个项目插入到现有的有序数组中。我意识到我可以创建一个全新的数组并重新对所有对象进行排序，但这不是我的目标。谢谢!

  9. ruby - 如何排序不是简单的哈希(哈希的哈希) - 2

    我有一个这样的哈希{55=>{:value=>61,:rating=>-147},89=>{:value=>72,:rating=>-175},78=>{:value=>64,:rating=>-155},84=>{:value=>90,:rating=>-220},95=>{:value=>39,:rating=>-92},46=>{:value=>97,:rating=>-237},52=>{:value=>73,:rating=>-177},64=>{:value=>69,:rating=>-167},86=>{:value=>68,:rating=>-165},53=>{:va

  10. ruby - 根据值然后键对ruby中的哈希进行排序 - 2

    如何在ruby​​中先根据值然后根据键对散列进行排序？例如h={4=>5,2=>5,7=>1}将排序为[[7,1],[2,5],[4,5]]我可以根据值进行排序h.sort{|x,y|x[1]y[1]}但我不知道如何根据值进行排序，然后在值相同时键入 最佳答案 h.sort_by{|k,v|[v,k]}这使用了Array的事实混入Comparable并定义逐元素。注意上面等价于h.sort_by{|el|el.reverse}相当于h.sort_by(&:reverse)这可能会或可能不会更具可读性。如果你知道Hashes一般都是先

随机推荐