排序算法-冒泡排序

冒泡排序

1、基本介绍

1. 思路：

   通过对待排序序列从前向后（从小标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒

2. 原理：

   比较两个相邻的元素，将值大的元素交换至右端。

3. 性能

   1.如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。

   2.如果很不幸我们的数据是反序的，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：冒泡排序的最坏时间复杂度为：O(n2) 。

   综上所述：冒泡排序总的平均时间复杂度为：O(n2)

2、举例

排序数组：int[]arr={6,3,8,2,9,1};第一趟排序： 第一次排序：6和3比较，6大于3，交换位置：368291第二次排序：6和8比较，6小于8，不交换位置：368291第三次排序：8和2比较，8大于2，交换位置：362891第四次排序：8和9比较，8小于9，不交换位置：362891第五次排序：9和1比较：9大于1，交换位置：362819第一趟总共进行了5次比较， 排序结果：362819--------------------------------------------------------------------- 第二趟排序： 第一次排序：3和6比较，3小于6，不交换位置：362819第二次排序：6和2比较，6大于2，交换位置：326819第三次排序：6和8比较，6大于8，不交换位置：326819第四次排序：8和1比较，8大于1，交换位置：326189第二趟总共进行了4次比较， 排序结果：326189--------------------------------------------------------------------- 第三趟排序： 第一次排序：3和2比较，3大于2，交换位置：236189第二次排序：3和6比较，3小于6，不交换位置：236189第三次排序：6和1比较，6大于1，交换位置：231689第二趟总共进行了3次比较， 排序结果：231689--------------------------------------------------------------------- 第四趟排序： 第一次排序：2和3比较，2小于3，不交换位置：231689第二次排序：3和1比较，3大于1，交换位置：213689第二趟总共进行了2次比较， 排序结果：213689--------------------------------------------------------------------- 第五趟排序： 第一次排序：2和1比较，2大于1，交换位置：123689第二趟总共进行了1次比较， 排序结果：123689--------------------------------------------------------------------- 最终结果：123689---------------------------------------------------------------------

3、代码实现

第一版

publicclassBubbleSortNormal{6publicstaticvoidmain(String[]args){7int[]list={3,4,1,5,2};8inttemp=0;// 开辟一个临时空间, 存放交换的中间值9// 要遍历的次数10for(inti=0;i<list.length-1;i++){11System.out.format("第 %d 遍：\n",i+1);12//依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上13for(intj=0;j<list.length-1-i;j++){14// 比较相邻的元素，如果前面的数小于后面的数，就交换15if(list[j]<list[j+1]){16temp=list[j+1];17list[j+1]=list[j];18list[j]=temp;19}20System.out.format("第 %d 遍的第%d 次交换：",i+1,j+1);21for(intcount:list){22System.out.print(count);23}24System.out.println("");25}26System.out.format("第 %d 遍最终结果：",i+1);27for(intcount:list){28System.out.print(count);29}30System.out.println("\n#########################");31}32}33}

思路 外层循环：即主循环，需要辅助我们找到当前第 i 小的元素来让它归位。所以我们会一直遍历 n-2 次，这样可以保证前 n-1 个元素都在正确的位置上，那么最后一个也可以落在正确的位置上了。 内层循环：即副循环，需要辅助我们进行相邻元素之间的比较和换位，把大的或者小的浮到水面上。所以我们会一直遍历 n-1-i 次这样可以保证没有归位的尽量归位，而归位的就不用再比较了。 而上面的问题，出现的原因也来源于这两次无脑的循环，正是因为循环不顾一切的向下执行，所以会导致在一些特殊情况下得多余。例如5，4，3，1，2 的情况下，常规版会进行四次循环，但实际上第一次就已经完成排序了。

运行结果

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-q7cCwWoD-1616402033671)(https://t-images-1304141946.cos.ap-hongkong.myqcloud.com/blog/1378215-20190726141202260-350678717.png)]

优化一

publicclassBubbleSoerOpt1{6publicstaticvoidmain(String[]args){7int[]list={5,4,3,1,2};8inttemp=0;// 开辟一个临时空间, 存放交换的中间值9// 要遍历的次数10for(inti=0;i<list.length-1;i++){11intflag=1;//设置一个标志位12//依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上13for(intj=0;j<list.length-1-i;j++){14// 比较相邻的元素，如果前面的数小于后面的数，交换15if(list[j]<list[j+1]){16temp=list[j+1];17list[j+1]=list[j];18list[j]=temp;19flag=0;//发生交换，标志位置020}21}22System.out.format("第 %d 遍最终结果：",i+1);23for(intcount:list){24System.out.print(count);25}26System.out.println("");27if(flag==1){//如果没有交换过元素，则已经有序28return;29}3031}32}33}

运行结果：可以看到优化效果非常明显，比正常情况下少了两次的循环。

这个时候我们就来讨论一下上面留下的一个小地方！没错就是最优时间复杂度为O(n)的问题，我们在进行了这一次算法优化之后，就可以做到了。

当给我们一个数列，5，4，3，2，1，让我们从大到小排序。没错，这是已经排好序的啊，也就是说因为标志位的存在，上面的循环只会进行一遍，flag没有变成1，整个算法就结束了，这也就是 O(n) 的来历了！

优化二

​ 在冒泡排序中还有一个问题存在，就是第 i 趟排的第 i 小或者大的元素已经在第 i 位上了，甚至可能第 i-1 位也已经归位了，那么在内层循环的时候，有这种情况出现就会导致多余的比较出现。例如：6，4，7，5，1，3，2，当我们进行第一次排序的时候，结果为6，7，5，4，3，2，1，实际上后面有很多次交换比较都是多余的，因为没有产生交换操作。

解决：

我们可以想到，利用一个标志位，记录一下当前第 i 趟所交换的最后一个位置的下标，在进行第 i+1 趟的时候，只需要内循环到这个下标的位置就可以了，因为后面位置上的元素在上一趟中没有换位，这一次也不可能会换位置了。基于这个原因，我们可以进一步优化我们的代码。

publicclassBubbleSoerOpt2{6publicstaticvoidmain(String[]args){7int[]list={6,4,7,5,1,3,2};8intlen=list.length-1;9inttemp=0;// 开辟一个临时空间, 存放交换的中间值10inttempPostion=0;// 记录最后一次交换的位置11// 要遍历的次数12for(inti=0;i<list.length-1;i++){13intflag=1;//设置一个标志位14//依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上15for(intj=0;j<len;j++){16// 比较相邻的元素，如果前面的数小于后面的数，交换17if(list[j]<list[j+1]){18temp=list[j+1];19list[j+1]=list[j];20list[j]=temp;21flag=0;//发生交换，标志位置022tempPostion=j;//记录交换的位置23}24System.out.format("第 %d 遍第%d 趟结果：",i+1,j+1);25for(intcount:list){26System.out.print(count);27}28System.out.println("");29}30len=tempPostion;//把最后一次交换的位置给len，来缩减内循环的次数31System.out.format("第 %d 遍最终结果：",i+1);32for(intcount:list){33System.out.print(count);34}35System.out.println("");36if(flag==1){//如果没有交换过元素，则已经有序37return;38}3940}41}42}