排序算法之详解冒泡排序

引入

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

思路

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

冒泡排序.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;
}

原文链接:https://www.cnblogs.com/fzdkx/p/17352267.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:排序算法之详解冒泡排序 - Python技术站

(0)
上一篇 2023年4月25日
下一篇 2023年4月25日

相关文章

  • 详解Java中字典树(Trie树)的图解与实现

    详解Java中字典树(Trie树)的图解与实现 一、什么是字典树(Trie树) 字典树,又称为Trie树,是一种树形数据结构。常用于统计和排序大量的字符串。它支持快速插入和查找,并且可以用于词频统计。 二、字典树的基本性质 根节点不包含字符,除根节点外每个节点都只包含一个字符。 从根节点到某个节点,路径上经过的字符连接起来,为该节点对应的字符串。 每个节点的…

    数据结构 2023年5月17日
    00
  • java编程队列数据结构代码示例

    下面是“Java编程队列数据结构代码示例”的完整攻略。 什么是队列 队列是一种有序的数据结构,特点是先进先出(FIFO)。队列中不管是插入操作还是删除操作,都是在队列的两端进行的,插入操作在队列的尾部进行,删除操作在队列的头部进行。队列的一个重要用途是在计算机的操作系统中,实现进程和所有需要等待资源的实体之间的交互。 队列的实现 队列数据结构可以采用数组或链…

    数据结构 2023年5月17日
    00
  • C++数据结构之链表的创建

    C++中链表的创建一般可分为以下几个步骤: 创建节点结构体 创建链表类,定义私有变量头结点(head)和一些公有方法,如插入、删除和打印链表等 实现链表的插入、删除和打印方法 下面将会对以上每个步骤进行详细讲解。 1. 创建节点结构体 节点结构体包含两个部分,一个是存储数据的变量,另一个是存储指向下一个节点的指针。代码如下: struct Node { in…

    数据结构 2023年5月17日
    00
  • Java数据结构与算法入门实例详解

    Java数据结构与算法入门实例详解攻略 概述 本攻略主要介绍Java数据结构与算法入门实例详解,包括学习的目标、适合的人群、学习方法等。通过本攻略的学习,可以更好地掌握Java数据结构和算法的基本知识,提升编程水平。 学习目标 本攻略的学习目标为: 掌握Java基础数据结构,如数组、链表、栈、队列等; 理解并掌握常见算法,如排序、查找、递归等; 掌握Java…

    数据结构 2023年5月17日
    00
  • Python三数之和的实现方式

    Python三数之和的实现方式 三数之和是一道经典的算法问题,其目标是在一个数组中找到三个数,使它们为0。本文将介绍两种Python实现三数之和的方法。 方法一:暴力枚举 最简单的方法是使用重循环枚举所有可能的三元组,并检查它们的和是否为0。这种方法的时间复杂度为O(n^3),不用于大型数组。 下面是一个示例,用于演示如何使用暴力枚举实现三数之和。 def …

    python 2023年5月14日
    00
  • Python数据结构与算法中的栈详解(2)

    Python数据结构与算法中的栈详解(2) 本文将深入探讨栈的应用和实现。我们将介绍栈在括号匹配、函数调栈、逆波兰表达式求值和中缀表达式转换为逆波兰表达式中的应用,并提供使用列表和链表实现栈的示例。 栈应用 1. 括号匹配 栈可以用于检查括号是否匹配。我们可以遍历字符串中的每个字符,如果是左括号,则将其压入栈中;如果是右括号,则将其与栈顶元素进行匹配。如果匹…

    python 2023年5月14日
    00
  • Python实现的排列组合计算操作示例

    下面是详细讲解“Python实现的排列组合计算操作示例”的完整攻略。 1. 什么是排列组合 排列组合是数学中的一个分支,它研究是从组元素中选取若干个元素进行排列或组合的和规律。在实际应用中,排列组合经用计算概率、统计学、密码学等领域。 2. Python实现排列组计算 Python中有多种方法可以排列组合计算,以下是其中两种常用的方法。 2.1math库实现…

    python 2023年5月14日
    00
  • Python基于均值漂移算法和分水岭算法实现图像分割

    下面是详细讲解“Python基于均值漂移算法和分水岭算法实现图像分割”的完整攻略,包括算法原理、Python实现和两个示例。 算法原理 图像分割是指将一幅图像分成若干个互不重叠的区域,每个区域内的像素具有相似的特征。均值漂移算法和分水岭算法是两种常用的图像分割算法。 均值漂移算法 均值漂移算法是一种基于密度估计的非参数法,其主要思想是通过对数据点进行密度估计…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部