冒泡排序1、基本介绍思路通过对待排序序列从前向后从小标较小的元素开始依次比较相邻元素的值若发现逆序则交换使值较大的元素逐渐从前移向后部就像水底下的气泡一样逐渐向上冒原理比较两个相邻的元素将值大的元素交换至右端。性能1.如果我们的数据正序只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值即Cminn-1;Mmin0;所以冒泡排序最好的时间复杂度为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};8inttemp0;// 开辟一个临时空间, 存放交换的中间值9// 要遍历的次数10for(inti0;ilist.length-1;i){11System.out.format(第 %d 遍\n,i1);12//依次的比较相邻两个数的大小遍历一次后把数组中第i小的数放在第i个位置上13for(intj0;jlist.length-1-i;j){14// 比较相邻的元素如果前面的数小于后面的数就交换15if(list[j]list[j1]){16templist[j1];17list[j1]list[j];18list[j]temp;19}20System.out.format(第 %d 遍的第%d 次交换,i1,j1);21for(intcount:list){22System.out.print(count);23}24System.out.println();25}26System.out.format(第 %d 遍最终结果,i1);27for(intcount:list){28System.out.print(count);29}30System.out.println(\n#########################);31}32}33}思路 外层循环即主循环需要辅助我们找到当前第 i 小的元素来让它归位。所以我们会一直遍历 n-2 次这样可以保证前 n-1 个元素都在正确的位置上那么最后一个也可以落在正确的位置上了。 内层循环即副循环需要辅助我们进行相邻元素之间的比较和换位把大的或者小的浮到水面上。所以我们会一直遍历 n-1-i 次这样可以保证没有归位的尽量归位而归位的就不用再比较了。 而上面的问题出现的原因也来源于这两次无脑的循环正是因为循环不顾一切的向下执行所以会导致在一些特殊情况下得多余。例如54312 的情况下常规版会进行四次循环但实际上第一次就已经完成排序了。运行结果[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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};8inttemp0;// 开辟一个临时空间, 存放交换的中间值9// 要遍历的次数10for(inti0;ilist.length-1;i){11intflag1;//设置一个标志位12//依次的比较相邻两个数的大小遍历一次后把数组中第i小的数放在第i个位置上13for(intj0;jlist.length-1-i;j){14// 比较相邻的元素如果前面的数小于后面的数交换15if(list[j]list[j1]){16templist[j1];17list[j1]list[j];18list[j]temp;19flag0;//发生交换标志位置020}21}22System.out.format(第 %d 遍最终结果,i1);23for(intcount:list){24System.out.print(count);25}26System.out.println();27if(flag1){//如果没有交换过元素则已经有序28return;29}3031}32}33}运行结果可以看到优化效果非常明显比正常情况下少了两次的循环。这个时候我们就来讨论一下上面留下的一个小地方没错就是最优时间复杂度为O(n)的问题我们在进行了这一次算法优化之后就可以做到了。当给我们一个数列54321让我们从大到小排序。没错这是已经排好序的啊也就是说因为标志位的存在上面的循环只会进行一遍flag没有变成1整个算法就结束了这也就是 O(n) 的来历了优化二​ 在冒泡排序中还有一个问题存在就是第 i 趟排的第 i 小或者大的元素已经在第 i 位上了甚至可能第 i-1 位也已经归位了那么在内层循环的时候有这种情况出现就会导致多余的比较出现。例如6475132当我们进行第一次排序的时候结果为6754321实际上后面有很多次交换比较都是多余的因为没有产生交换操作。解决我们可以想到利用一个标志位记录一下当前第 i 趟所交换的最后一个位置的下标在进行第 i1 趟的时候只需要内循环到这个下标的位置就可以了因为后面位置上的元素在上一趟中没有换位这一次也不可能会换位置了。基于这个原因我们可以进一步优化我们的代码。publicclassBubbleSoerOpt2{6publicstaticvoidmain(String[]args){7int[]list{6,4,7,5,1,3,2};8intlenlist.length-1;9inttemp0;// 开辟一个临时空间, 存放交换的中间值10inttempPostion0;// 记录最后一次交换的位置11// 要遍历的次数12for(inti0;ilist.length-1;i){13intflag1;//设置一个标志位14//依次的比较相邻两个数的大小遍历一次后把数组中第i小的数放在第i个位置上15for(intj0;jlen;j){16// 比较相邻的元素如果前面的数小于后面的数交换17if(list[j]list[j1]){18templist[j1];19list[j1]list[j];20list[j]temp;21flag0;//发生交换标志位置022tempPostionj;//记录交换的位置23}24System.out.format(第 %d 遍第%d 趟结果,i1,j1);25for(intcount:list){26System.out.print(count);27}28System.out.println();29}30lentempPostion;//把最后一次交换的位置给len来缩减内循环的次数31System.out.format(第 %d 遍最终结果,i1);32for(intcount:list){33System.out.print(count);34}35System.out.println();36if(flag1){//如果没有交换过元素则已经有序37return;38}3940}41}42}