排序算法之详解冒泡排序

引入

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

思路

  • 一组无序的数组,要求我们从小到大排列
    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日

相关文章

  • C语言实现学生信息管理系统(链表)

    C语言实现学生信息管理系统(链表) 简介 学生信息管理系统是管理学生的一种系统,可以实现添加、查找、删除和修改学生信息等功能。本文将使用C语言实现学生信息管理系统,并通过链表的方式进行实现。 前提条件 在开始之前,我们需要了解如下内容: C语言基础知识 链表的基本概念和使用 系统架构 学生信息管理系统主要包含以下几个模块: 学生信息结构体 添加学生信息 查找…

    数据结构 2023年5月17日
    00
  • Python实现隐马尔可夫模型的前向后向算法的示例代码

    Python实现隐马尔可夫模型的前向后向算法 隐马尔可夫模型(Hidden Markov Model,HMM)是一种常用的统计模型,它可以用于序列数据的建模和预测。在这篇文章中,我们将介绍如何使用Python实现隐马尔可夫模型的前向后向算法,并详细讲解实现原理。 实现原理 隐马尔可夫模型是一种基于状态转移的模型,它包含两个部分:状态序列和观测序列。状态序列是…

    python 2023年5月14日
    00
  • 数位dp

    数位dp 思想 一般来说,题目是要求在区间\([l,r]\)中符合某一种条件的数的个数 我们用前缀和的思想考虑,分别求出\([1,r]\)和\([1,l-1]\)中数的个数相减即为所求 这里采用记忆化搜索的方式实现 模板 #include<iostream> #include<cstring> #include<vector&g…

    算法与数据结构 2023年4月17日
    00
  • 使用python实现kmean算法

    K均值聚类算法是一种常用的无监督学习算法,它可以将数据集分成K个簇,每个簇包含最接近其质心的数据点。在本文中,我们将介绍如何使用Python实现K均值聚类算法。 步骤1:导入必要的库 在实现K均值聚类算法之前,我们需要导入必要的库。在这个例子中,我们将使用numpy和matplotlib库。numpy库用于处理数值计算,matplotlib库用于绘制图表。我…

    python 2023年5月14日
    00
  • Java数据结构之优先级队列(堆)图文详解

    Java数据结构之优先级队列(堆)图文详解 什么是优先级队列(堆) 优先级队列(堆)是一种非常重要的数据结构,它能够更好地管理数据,分配任务等。优先级队列的本质就是一种特殊的队列,它是一种可以根据元素的优先级来出队的数据结构。 通常情况下,队列中存储了一系列具有优先级的数据。当我们从队列中取出元素时,优先级高的元素会先出队。因此,我们需要一种数据结构,来对这…

    数据结构 2023年5月17日
    00
  • Python cookbook(数据结构与算法)同时对数据做转换和换算处理操作示例

    Python Cookbook:数据结构与算法 Python Cookbook是一本非常实用的Python编程指南,其中包含了许多有用的技巧和示例。本文将介绍其中一些有关数据结构和法的示例,包括如同时对数据做转换和换算处理操作。 示例1:使用生成器表达式对数据做转换和换算处理 有时候,我们需要对一些数据做转换和换算处理,例如将一个列表中的所有元素都转换为浮点…

    python 2023年5月14日
    00
  • 基于Python的图像阈值化分割(迭代法)

    下面是详细讲解“基于Python的图像阈值化分割(迭代法)”的完整攻略。 1. 什么是图像阈值分割 图像阈值分割是将图像分成两个或多个部分的过程,其中每个部分都具有不同的灰度级。阈值化分割是图像处理中最基本的操作之一,它可以用于图像增强、目标检测、图像分割等领域。 2. 迭代法阈值化分割 迭代法阈值化分割是一种基于图像直方图的分割方法,它通过迭代计算图像的全…

    python 2023年5月14日
    00
  • Python利用scikit-learn实现近邻算法分类的示例详解

    以下是关于“Python利用scikit-learn实现近邻算法分类的示例详解”的完整攻略: 简介 近邻算法是一种用于分类和回归的机器学习算法,它可以根据最近的邻居来预测新数据点的标签或值。在本教程中,我们将介绍如何使用Python和scikit-learn库实现近邻算法分类,并提供两个示例说明。 实现近邻算法分类 以下是使用Python和scikit-le…

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