Java排序之冒泡排序_java冒泡排序怎么排

createh53周前 (02-26)技术教程4

今天来给大家介绍一下排序算法之冒泡排序

jwt简介

冒泡排序:(Bubble Sort)是一种简单的交换排序。之所以叫做冒泡排序,因为我们可以把每个元素当成一个小气泡,根据气泡大小,一步一步移动到队伍的一端,最后形成一定对的顺序。

冒泡排序的原理:

我们以一个队伍站队为例,教官第一次给队员排队是无序的,这时候就需要排队,按矮到高的顺序排列,首先拎出第一第二个比较,如果第一个队员比第二个要高,则两个交换位置, 高的放到排到第二个位置,矮的就排到第一个,再把第二个,第三个比较,把高的排到后面一个位置,然后以此类推,直至第一轮所有队员都比较过一次(记住每次比较都是相邻的两个),这样就可以把最高的排到最后的位置。

总结就是: 每一轮都需要从第一位开始进行相邻的两个数的比较,将较大的数放后面,比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系,重复此步骤,直到最后一个还没归位的数。

冒泡排序流程图

我们进行分解看看每一步是怎么执行的

首先我们给个无序数组 [3,14,32,16,53,8] 进行升序排序

  • 第一轮:初始值 [3,14,32,16,53,8]

如图所示,走完第一轮之后,我们得到的结果就是[3,14,16,32,8,53],此时已经将最大的数53排到了指定位置,所以冒泡排序每一轮只能确定将一个数归位。即第一趟只能确定将末位上的数归位, 第二趟只能将倒数第 2 位上的数归位,依次类推下去

  • 第二轮:初始值 [3,14,16,32,8,53]第二轮排序结果[3,14,16,8,32,53]
  • 第三轮:初始值 [3,14,16,8,32,53]第三轮排序结果[3,14,8,16,32,53]
  • 第四轮:初始值 [3,14,8,16,32,53]第四轮排序结果[3,8,14,16,32,53]
  • 第五轮:初始值 [3,8,14,16,32,53]第五轮排序结果[3,8,14,16,32,53] 到这,我们最终排序完成。

Java代码实现:

 public static void bubbleSort(int[] array){
         for(int i=0;i array[j+1]){
                   //换位
                     int temp = array[j];
                     array[j] = array[j+1];
                     array[j+1] = temp;
                 }
                 //比较一次,加1
                 num =num+1;
 
             }
             //结果输出
             System.out.print("第"+(i+1)+"轮:[");
             for (int a=0;a

输出结果

   第1轮结果:[3,14,16,32,8,53],每轮比较了:5 次
   第2轮结果:[3,14,16,8,32,53],每轮比较了:5 次
   第3轮结果:[3,14,8,16,32,53],每轮比较了:5 次
   第4轮结果:[3,8,14,16,32,53],每轮比较了:5 次
   第5轮结果:[3,8,14,16,32,53],每轮比较了:5 次

我在每轮比较的时候定义了一个num来记录比较次数,大家可以看到长度为6的数组比较,比较了5轮,每轮都比较了5次, 但是通过上面拆分的每一轮比较细节可以看出,其实约到后面的比较,有一部分已经是排好了,如果某个数比他的下一个位置还小, 就没有必要和后面已经排好的数据再做比较,这样只会增加程序运行压力。

比如,第四轮,8和14比较,换位之后,16,32,53都已经排好了,14再和16比较,不用换位,那16之后的数据已经在第三轮排好,就没必要再比较16和32,32和53了。

那我们来对程序做一个优化,其实在第一轮把最大的数字排到最后之后,第二轮就不用再和最后一个数字比较,因为最大的数字已经排好,再比较也只能排在最后一位之前了。

优化: 我们就在程序内层循环做一个限制,每轮比较之后,下一轮就比较到array.length-1-i的位置。就是第一轮6位数都比较完成,最大排在最后,第二轮就比较前五个数,把前五个数中最大的排在第五位。这样以此类推,就可以减少程序中无用的比较。

优化代码如下:

   public static void bubbleSort(int[] array){
         for(int i=0;i

我们再来看看结果:

第1轮结果:[3,14,16,32,8,53],每轮比较了:5 次
第2轮结果:[3,14,16,8,32,53],每轮比较了:4 次
第3轮结果:[3,14,8,16,32,53],每轮比较了:3 次
第4轮结果:[3,8,14,16,32,53],每轮比较了:2 次
第5轮结果:[3,8,14,16,32,53],每轮比较了:1 次

由此,我们可以看到,由之前30次比较减少到15次,所以程序压力会少很多,程序复杂度也降低了。由上面结果可知:6位长度的数组需要排五轮,每轮次数减1,那如果由n个长度的数组,需要比较多少次呢?

  1. 第一轮:6-1
  2. 第二轮:6-2
  3. 第三轮:6-3
  4. 倒数第二轮:2
  5. 倒数第一轮:1

得出结果:(n-1)+(n-2)+...+2+1 = n(n-1)/2 =1/2n^2 -1/2n
是一个等差数列,按照时间复杂度规则,直接取最高阶项并去除常熟系数等到时间复杂度就是 O(n^2)了

到这,我们的冒泡排序就了解完了。

相关文章

Java常用的7大排序算法汇总_java常见的排序算法

这段时间闲了下来,就抽了点时间总结了下java中常用的七大排序算法,希望以后可以回顾!1.插入排序算法插入排序的基本思想是在遍历数组的过程中,假设在序号 i 之前的元素即 [0..i-1] 都已经排好...

JAVA 冒泡排序_Java冒泡排序法

1 概念冒泡排序(Bubble Sort),是计算机科学领域中较简单的一种排序算法。它重复地走访需要进行排序的元素,依次比较两个相邻的元素,如果元素的顺序(如从大到小、首字母从A到Z)错误就把元素的位...

堆排序实战:轻松实现高效排序,附详细Java代码

#每日读书打卡#Hello,大家好!我是你们的小米,今天又来给大家分享干货啦!最近很多小伙伴们都对排序算法产生了浓厚的兴趣,继上次分享了“手写快排”之后,今天我们再来搞搞堆排(Heap Sort),...

java数据结构与算法之希尔排序_希尔排序csdn

希尔排序概述希尔排序因计算机科学家Donald1.Shell而得名,他在1959年发现了希尔排序算法。希尔排序基于插入排序,但是增加了一个新的特性,大大地提高了插入排序的执行效率。依靠这个特别的实现机...

八种经典排序算法总结,妈妈再也不用担心我不会了

前言算法和数据结构是一个程序员的内功,所以经常在一些笔试中都会要求手写一些简单的排序算法,以此考验面试者的编程水平。下面我就简单介绍八种常见的排序算法,一起学习一下。一、冒泡排序思路:比较相邻的元素。...

深圳尚学堂Java培训:排序方法小结-插入排序

插入排序工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。就是将数组第一个值看做有序的,从后每一个值放进来的时候,找放的位置。这里边就需要一些已经排好的数据可...