Java最简洁数据结构之冒泡排序快速理解

目录
  • 一、什么是冒泡排序
  • 二、图解冒泡排序
  • 三、代码实现
  • 四、代码的优化
    • 1、整体的思路
    • 2、代码示例

一、什么是冒泡排序

冒泡排序的英文是bubble sort，它是一种基础的交换排序。说到冒泡是不是就想起了快乐肥宅水呢？汽水中有许多小小的水泡哗啦哗啦的浮到上面来。这是因为组成小气泡的二氧化碳比水轻，所以小气泡可以一点一点地向上浮动。

而冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身的大小，一点一点的向着数组的一侧移动。

二、图解冒泡排序

我们先看一个例子，有七个数字组成一个无序数列{5，6，3，4，1，7}，对他进行冒泡排序。

按照冒泡排序的思想：把相邻的两个数字两两比较，当一个数字大于右侧相邻的数字时，交换他们的位置，当一个数字和他右侧的数字小于或等于的时候，不交换。

这样，作为数列中的最大的数字7就交换到了最右侧。这时第一轮冒泡结束。（有效区域只有最后一个）

根据第一轮的交换细节，第二轮到第六轮的状态为下图。

到此为止，所有的数字都是有序的了，冒泡排序是一种稳定排序，由于该排序算法的每一轮都要遍历所有的数字，一共要遍历n-1，所以时间复杂度为O(n^2)。

那么我们如何区分排序算法是否稳定呢？

如果我们交换的时候，遇到两个相同的数字，如果两个相同的数字在排序之后相对位置没有交换，那么就是稳定的排序，反之则是不稳定的排序。

三、代码实现

    public static void bubbleSort(int arr[]){
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j <arr.length-i-1 ; j++) {
                int tmp=0;
                if(arr[j]>arr[j+1]){
                    tmp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5,6,3,2,4,1,7};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

四、代码的优化

1、整体的思路

从上面的例子不难看出，我们可以对原来的冒泡排序进行优化。我们仍然用上面呢个数列{5，6，3，4，1，7}为例子，从上面的图解可以看出在第五轮排序后，整个数列已经是有序的，但是排序算法还是执行了第六轮排序。

优化的思路是：如果能判断出数列已经是有序的了，并且做出标记，那么就不会执行多余的排序。

所以我们可以用布尔变量isSorted作为标记，如果在本轮排序中有元素进行交换，则说明数列无序；如果在本轮排序中，没有元素进行交换，我们则认为此时数列已经为有序的，不需要再去进行下一轮的排序。

2、代码示例

    public static void bubbleSort(int arr[]){
        for (int i = 0; i < arr.length-1; i++) {
            //有序标记，每一轮的初始值都是true
            boolean isSorted=true;
            for (int j = 0; j < arr.length-i-1; j++) {
                int tmp=0;
                if (arr[j]>arr[j+1]){
                    tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                    //因为有元素进行交换，所以不是有序的，标记变为false
                    isSorted=false;
                }
            }
            if (isSorted){
                break;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[]{5,6,3,2,4,1,7};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

以上就是Java最简洁数据结构之冒泡排序快速理解的详细内容，更多关于Java 冒泡排序的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Java 实战项目锤炼之网上花店商城的实现流程

    Java 实战项目锤炼之网上花店商城的实现流程

    一.项目简述 功能: 一套完整的网上花店商场系统,系统支持前台会员的注册 登陆系统留言,花朵的品种选择,详情浏览,加入购物 车,购买花朵等:后台支持管理员的花朵种类添加,花朵 详情的添加修改,用户管理,留言管理,商场新闻管理等. 二.项目运行 环境配置: Jdk1.8 + Tomcat8.5 + mysql + Eclispe (IntelliJ IDEA,Eclispe,MyEclispe,Sts 都支持) 项目技术: JSP + Servlert + html+ css + JavaScri

  • Java 实战项目锤炼之医院门诊收费管理系统的实现流程

    Java 实战项目锤炼之医院门诊收费管理系统的实现流程

    一.项目简述 功能:登录,门诊划价,收费,报表,药品管理等等功能. 二.项目运行 运行环境: Jdk1.8 + Tomcats . 5 + mysql + Eclispe ( IntelliJ IDEA ,Eclispe , MyEclispe , sts 都支持). 项目技术: JSP + Entity + Servlert + html + css + Javascript + JQuery + Ajax +「 ileupload 等等. 药品操作代码: //药品操作 @Controller

  • Java 实战项目之仓库管理系统的实现流程

    Java 实战项目之仓库管理系统的实现流程

    一.项目简述 功能包括: 仓库管理,出入库管理,仓库人员管理,基本信息管理, 供应商信息,系统管理等等. 二.项目运行 环境配置: Jdk1.8 + Tomcat8.5 + mysql + Eclispe (IntelliJ IDEA,Eclispe,MyEclispe,Sts 都支持) 项目技术: JSP +Spring + SpringMVC + MyBatis + html+ css + JavaScript + JQuery + Ajax + layui+ maven等等. 客户信息管理

  • Java 实战项目锤炼之在线购书商城系统的实现流程

    Java 实战项目锤炼之在线购书商城系统的实现流程

    一.项目简述 功能:一个基于JavaWeb的网上书店的设计与实现,归纳 出了几个模块,首先是登录注册模块,图书查找模块,购 物车模块,订单模块,个人中心模块,用户管理模块,图 书管理模块等. 该项目是javaJeb技术的实战操作,采用了MVC设计模 式,包括基本的entity, jscript, servlet,以及ajax异步请 求,查询分页,持久化层方法的封装等等,对javaweb技 术的巩固很有帮助,为J2EE的学习打下基础,适用于课程 设计,毕业设计. 二.项目运行 环境配置: Jdk1

  • Java 实战项目锤炼之小区物业管理系统的实现流程

    Java 实战项目锤炼之小区物业管理系统的实现流程

    一.项目简述 功能包括: 分为管理员及普通业主角色,业主信息,社区房屋,维护 管理,社区车辆,社区投诉,社区缴费,社区业务信息维 护等等功能. 二.项目运行 环境配置: Jdk1.8 + Tomcat8.5 + mysql + Eclispe (IntelliJ IDEA,Eclispe,MyEclispe,Sts 都支持) 项目技术: JSP +Spring + SpringMVC + MyBatis + html+ css + JavaScript + JQuery + Ajax + mav

  • Java 实战项目锤炼之嘟嘟健身房管理系统的实现流程

    Java 实战项目锤炼之嘟嘟健身房管理系统的实现流程

    一.项目简述 功能包括: 前台+后台健身房管理系统,用户预订,教练选择.课程选 择,登录,后台管理等等. 二.项目运行 环境配置: Jdk1.8 + Tomcat8.5 + mysql + Eclispe (IntelliJ IDEA,Eclispe,MyEclispe,Sts 都支持) 项目技术: JSP +Spring + SpringMVC + MyBatis + html+ css + JavaScript + JQuery + Ajax + layui+ maven等等. 系统操作模块

  • Java 实战项目锤炼之在线美食网站系统的实现流程

    Java 实战项目锤炼之在线美食网站系统的实现流程

    一.项目简述 功能:用户的注册登录,美食浏览,美食文化,收藏百 科,趣味问答,食谱等等功能等等. 二.项目运行 环境配置: Jdk1.8 + Tomcat8.5 + mysql + Eclispe (IntelliJ IDEA,Eclispe,MyEclispe,Sts 都支持) 项目技术: JSP +Springboot+ SpringMVC + MyBatis + ThymeLeaf + FTP+ JavaScript + JQuery + Ajax + maven等等. 评论控制器: /*

  • Java 实战项目锤炼之在线蛋糕商城系统的实现

    Java 实战项目锤炼之在线蛋糕商城系统的实现

    一.项目简述 功能: 主页显示热销商品:所有蛋糕商品展示,可进行商品搜 索:点击商品进入商品详情页,具有立即购买和加入购物 车功能,可增减购买商品数量亦可手动输入(同时验证库 存),热销商品展示.立即购买进入确认订单页面,可选择 已经添加的地址,亦可新增地址.(同时验证库存),可选 择购买哪些商品,可删除不需要的商品.点击结算进入确 认订单页面,确认后提交订单.后台管理:(修改密码 等),商品管理(商品批量添加.上下架等),订单管理. 二.项目运行 环境配置: Jdk1.8 + Tomcat8.

  • Java最简洁数据结构之冒泡排序快速理解

    Java最简洁数据结构之冒泡排序快速理解

    目录 一.什么是冒泡排序 二.图解冒泡排序 三.代码实现 四.代码的优化 1.整体的思路 2.代码示例 一.什么是冒泡排序 冒泡排序的英文是bubble sort,它是一种基础的交换排序.说到冒泡是不是就想起了快乐肥宅水呢?汽水中有许多小小的水泡哗啦哗啦的浮到上面来.这是因为组成小气泡的二氧化碳比水轻,所以小气泡可以一点一点地向上浮动. 而冒泡排序之所以叫冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身的大小,一点一点的向着数组的一侧移动. 二.图解冒泡排序 我们先看一个例

  • 快速理解Java垃圾回收和jvm中的stw

    Java中Stop-The-World机制简称STW,是在执行垃圾收集算法时,Java应用程序的其他所有线程都被挂起(除了垃圾收集帮助器之外).Java中一种全局暂停现象,全局停顿,所有Java代码停止,native代码可以执行,但不能与JVM交互:这些现象多半是由于gc引起. GC时的Stop the World(STW)是大家最大的敌人.但可能很多人还不清楚,除了GC,JVM下还会发生停顿现象. JVM里有一条特殊的线程--VM Threads,专门用来执行一些特殊的VM Operation

  • 快速理解Java设计模式中的组合模式

    快速理解Java设计模式中的组合模式

    组合模式是一种常见的设计模式(但我感觉有点复杂)也叫合成模式,有时又叫做部分-整体模式,主要是用来描述部分与整体的关系. 个人理解:组合模式就是将部分组装成整体. 定义如下: 将对象组合成树形结构以表示"部分-整体"的层次结构,使得用户对单个对象和组合对象的使用具有一致性. 通用类图如下: 组合模式的包含角色: ● Component 抽象构件角色 定义参加组合对象的共有方法和属性,可以定义一些默认的行为或属性. ● Leaf 叶子构件 叶子对象,其下再也没有其他的分支,也就是遍历的最

  • 浅谈Java中常用数据结构的实现类 Collection和Map

    线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构.这些类均在java.util包中.本文试图通过简单的描述,向读者阐述各个类的作用以及如何正确使用这些类. Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ├Hashtable ├HashMap └WeakHashMap Collection接口 Collection是最基本的集合接口,一个C

  • java实现队列数据结构代码详解

    什么是队列结构 一种线性结构,具有特殊的运算法则[只能在一端(队头)删除,在另一端(队尾)插入]. 分类: 顺序队列结构 链式队列结构 基本操作: 入队列 出队列 给出一些应用队列的场景 1):当作业被送到打印机的时候,就可以按到达的顺序排起来,因此每一份作业是队列的节点. 2):售票口的人买票的顺序的按照先来先买的顺序售票. 3):当所有的终端被占用,由于资源有限,来访请求需要放在一个队列中等候. 队列是先进先出的! 我们设置一个叫做LinkQueue<T>的泛型集合类,该类里面有 Node

  • 快速理解spring中的各种注解

    快速理解spring中的各种注解

    Spring中的注解大概可以分为两大类: 1)spring的bean容器相关的注解,或者说bean工厂相关的注解: 2)springmvc相关的注解. spring的bean容器相关的注解,先后有:@Required, @Autowired, @PostConstruct, @PreDestory,还有Spring3.0开始支持的JSR-330标准javax.inject.*中的注解(@Inject, @Named, @Qualifier, @Provider, @Scope, @Singlet

  • python算法与数据结构之冒泡排序实例详解

    一.冒泡排序介绍 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 二.冒泡排序原理 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.这一步做完,最后的元素应该会是最大的数. 针对所有的

  • Java实现对两个List快速去重并排序操作示例

    Java实现对两个List快速去重并排序操作示例

    本文实例讲述了Java实现对两个List快速去重并排序操作.分享给大家供大家参考,具体如下: 1:去重并排序 package twolist; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.uti

  • Java集合和数据结构排序实例详解

    Java集合和数据结构排序实例详解

    目录 概念 插入排序 直接插入排序 代码实现 性能分析 希尔排序 代码实现 性能分析 选择排序 直接选择排序 代码实现 性能分析 堆排序 代码实现 性能分析 交换排序 冒泡排序 代码实现 性能分析 快速排序 代码实现 性能分析 非递归实现快速排序 代码实现 性能分析 归并排序 归并排序 代码实现 性能分析 非递归实现归并排序 代码实现 性能分析 海量数据的排序问题 总结 概念 排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作. 平时的上下文中,如果提到排序,通常

  • Java并发之synchronized实现原理深入理解

    Java并发之synchronized实现原理深入理解

    目录 synchronized的三种应用方式 synchronized作用于实例方法 synchronized作用于静态方法 synchronized同步代码块 synchronized底层语义原理 理解Java对象头与Monitor synchronized代码块底层原理 synchronized方法底层原理 Java虚拟机对synchronized的优化 偏向锁 轻量级锁 自旋锁 锁消除 关于synchronized 可能需要了解的关键点 synchronized的可重入性 线程中断与syn

随机推荐