【图灵干货】经典算法之冒泡排序
2021-12-05 15:19:04
冒泡排序是Java中一种非常经典的排序方法,它能对几个数进行升序排序,效率较高。
一、冒泡分类原则。
把两个相邻的数字比较大小,把两个数字中较大的数字放到右边,小的向左放。
二,冒泡分类的图示。
1.先定义int[]arr={4,2,5,3,1}
2.比较情况如下:
三、冒泡排序思想的解析。
按顺序将前两个数字的大小进行比较,如果后的数字小于前的数字,则把小的放在左,大的数字放在右,等等。
比如:int[]arr={4,2,5,3,1}
首次比较:
1.将arr[0]与arr[1]相比较,则2比4小,则2向左移动一位,4向右移动一位;
2.将其与arr[1]和arr[2]比较,目前是4比5,因此保持不动。
3.把arr[2]与arr[3]相比较,现在5比3大,因此3向左移一位,5向右移一位。
4.把arr[4]与arr[4]相比较,现在5比1大,因此将1移向左1,5移向后1,这使得最大数字放在最右侧*现在经过比较并进行移动后,数组arr中的元素就变为{2,4,3,1,5}
第2圈比较:
1.将arr[0]与arr[1]比较,2比4小,因此不必移动。
2.将arr[1]与arr[2]作比较,则4比3大,因此3向左移一位,4向右移一位。
3.将arr[2]与arr[3]作比较,则4比1大,因此将1向左移一位,4向右移一位。
*因为最大的已经位于最右侧,因此不必与arr[4]进行比较,现在通过第二圈比较后的数组元素变为。
{2,3,1,4,5}
*注意,第二圈比较的次数现在少了一次。
循环对比:
1.将arr[0]与arr[1]比较,2比3小,因此不必移动。
2.将arr[1]与arr[2]作比较,则3比1大,因此将1向左移一位,3向右移一位*现在通过第三圈的比较,数组中的元素变成{2,1,3,4,5}*注意,现在第三圈比较的次数又少了一次。
第4组比较:
1.将arr[0]与arr[1]作比较,因此2比1大,因此1向左移一位,2向右移一位。
*现在已经使用了第四圈的比较,数组中的元素变成了{1,2,3,4,5},所以比较完整。
这样就能从4圈中判断出我们的数组的长度是5,但我们比较了4次,所以我们可以肯定,我们在循环中比较4。
圈
因此,外层for循环可以确定为for(inti=0),i每圈比较的次数将比上一圈的比较少1次,因此可以推断。
a)在第一圈元素比较时,内循环的次数是数组长度-1。
b)在第二圈元素比较时,内循环的次数是数组长度-2。
c)类推,得出结论:在进行第n圈元素比较时,内循环的次数是-n。
因此,这一n的特征实际上与外层for循环中的i一致,因此我们的内存for循环就被确定为for(int i = 0,i<arr.length-1-i;i++)
四、构成代码。
//冒泡排序。
publicstaticvoidbubbleSort(int[]arr){
//功能
//外层循环用于控制数组循环的圈数。
for(inti=0;i//内循环用于完成元素值比较,并将大元素值交换到后面。
for(intj=0;jif(arr[j]>arr[j+1]){
inttemp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
五、总结
上面就是对冒泡排序的具体分析,学习冒泡排序需要梳理一下其过程,主要是分析如何比较冒泡排序。