一、冒泡排序的思想
思想:
从前到后(即从下标较小的元素开始)依次比较相邻元素的值,若发现逆序则交换位置,使值较大的元素逐渐从前移向后部。
eg:待排序的数:7,3,22,15,8
根据冒泡排序的思想:
首先我们应该比较7和3是否是逆序的:若逆序则交换这2个数的位置,因为7>3,它们的位置是逆序的故交换位置交换后:7,3, 22,15,8 3,7,22,15,8比较7和22是否是逆序的:若逆序则交换这2个数的位置,因为7<22,它们的位置是顺序的。故不用交换位置顺序仍为:3,7,22, 15,8 3,7,22, 15,8以此类推,思路分析会进行详细分析。二、冒泡排序的动画演示及思路分析
动画演示:
思路分析:
1.第一轮排序:22的位置被固定
7和3比较,若逆序则交换位置。因为7>3两数是逆序的,所以交换位置:7,3, 22,15,8 3,7, 22,15,87和22比较,若逆序则交换位置。因为7<22两数是顺序的,所以不交换位置:3, 7, 22, 15,8 3, 7, 22, 15,822和15比较,若逆序则交换位置。因为22>15两数是逆序的,所以交换位置:3,7, 22,15, 8 3,7, 15,22, 822和8比较,若逆序则交换位置。因为22>8两数是逆序的,所以交换位置:3,7, 15, 22,8 3,7, 15, 8,22第一轮排序后的结果:【22的位置被固定】3,7, 15, 8,22
2.第二轮排序:15的位置被固定
3和7比较若逆序则交换位置。因为3<7两数是顺序的,所以不交换位置:3,7, 15, 8,22 3,7, 15, 8,227和15比较若逆序则交换位置。因为7<15两数是顺序的,所以不交换位置:3, 7, 15, 8,22 3, 7, 15, 8,2215和8比较若逆序则交换位置。因为15>8两数是逆序的,所以交换位置:3, 7, 15, 8,22 3, 7, 8, 15,22第二轮排序后的结果:【15的位置被固定】3, 7, 8, 15, 22
3.第三轮排序:8的位置被固定
3和7比较若逆序则交换位置。因为3<7两数是顺序的,所以不交换位置:3,7, 8, 15,22 3,7, 8, 15,227和8比较若逆序则交换位置。因为7<8两数是顺序的,所以不交换位置:3, 7, 8,15,22 3, 7, 8,15,22第三轮排序后的结果:【8的位置被固定】:3, 7, 8,15, 22
4.第四轮排序:7的位置被固定
3和7比较若逆序则交换位置。因为3<7两数是顺序的,所以不交换位置:3,7, 8,15,22 3,7, 8,15,22第四轮排序后的结果:【7的位置被固定】:3,7, 8,15, 22
排序到此结束
思路总结 :
以上面的5个数为例,我们看到5个数进行排序需要进行4轮大的排序那么n个数排序时,需要进行 (n-1)轮大的排序。(1)上面五个数的第 一轮排序需进行4次(5个数参与排序,数组下标0-4)(2)上面五个数的第二轮排序需进行3次(4个数参与排序,数组下标0-3)(3)上面五个数的第三轮排序需进行2次(3个数参与排序,数组下标0-2)(4)上面五个数的第四轮排序需进行 1次(2个数参与排序,数组下标0-1)三、冒泡排序的代码+代码优化+代码详解
代码--————多个for循环分别控制排序:
结果:
优化代码(版本1)--————两个for循环嵌套控制排序:
优化分析:
第一轮排序:i
第二轮排序:i
第三轮排序:i
第四轮排序:i
所以可以用一个for循环嵌套在我们刚刚的for循环上
这个变量j的范围是0-3即
j < arr.length - 1
arr.length=5,j
j
代码:
结果:
优化代码(版本2)--————两个for循环嵌套+标志控制排序:
优化分析:
当第二轮排序完成后,数组已经是有序的。但是没有一个标志去告诉for循环,数组已经有序,该退出for循环了。所以针对这个问题,我们定义一个
boolean flag = false;
来判断是否结束for循环如果flag == false,说明数组已经有序,可以退出for循环了如果flag == true,我们需要让
flag=false;
以便下次数组有序时,可以退出for循环。
代码:
结果:
代码详解(优化版本2)
以7,3,22,15,8为例:
第一轮排序:22的位置被固定7和3比较,若逆序则交换位置。因为7>3两数是逆序的,所以交换位置:flag==true7,3, 22,15,8 3,7, 22,15,87和22比较,若逆序则交换位置。因为7<22两数是顺序的,所以不交换位置:flag==false(第一轮排序完成后才判断flag的值)3, 7, 22, 15,8 3, 7, 22, 15,822和15比较,若逆序则交换位置。因为22>15两数是逆序的,所以交换位置:flag==true3,7, 22,15, 8 3,7, 15,22, 822和8比较,若逆序则交换位置。因为22>8两数是逆序的,所以交换位置:flag==true3,7, 15, 22,8 3,7, 15, 8,22第一轮排序后flag==ture满足
所以flag=false,再开始第二轮排序
【22的位置被固定】3,7, 15, 8,22
第二轮排序:15的位置被固定3和7比较若逆序则交换位置。因为3<7两数是顺序的,所以不交换位置:flag==false(第二轮排序完成后才判断flag的值)3,7, 15, 8,22 3,7, 15, 8,227和15比较若逆序则交换位置。因为7<15两数是顺序的,所以不交换位置:flag==false(第二轮排序完成后才判断flag的值)3, 7, 15, 8,22 3, 7, 15, 8,2215和8比较若逆序则交换位置。因为15>8两数是逆序的,所以交换位置:flag==true3, 7, 15, 8,22 3, 7, 8, 15,22第二轮排序后flag==ture满足
所以flag=false,再开始第三轮排序【15的位置被固定】3, 7, 8, 15, 22
第三轮排序3和7比较若逆序则交换位置。因为3<7两数是顺序的,所以不交换位置:flag==false(第三轮排序完成后才判断flag的值)3,7, 8, 15,22 3,7, 8, 15,227和8比较若逆序则交换位置。因为7<8两数是顺序的,所以不交换位置:flag==false(第三轮排序完成后才判断flag的值)3, 7, 8,15,22 3, 7, 8,15,22第三轮排序后flag==false满足
所以退出第一个for循环,结束数组排序。输出排序后的结果。
到此冒泡排序的讲解就结束了~~