Java人工智能+Pythonweb前端UI/UE设计PHP+H5全栈工程师C/C++大数据新媒体软件测试产品经理电商运营网络安全+运维Go语言与区块链拍摄剪辑+短视频制作PMP项目管理认证iOSAndroid+物联网.NET

经典算法之冒泡排序

来源:黑马程序员

浏览245人

2020.05.20

冒泡排序是Java中非常经典的一种排序方法,可以将多个数字进行升序排序,效率比较高。

一、冒泡排序的原理

两个相邻的数比较大小,将两个数中较大的数往右边放,小的往左边放

二、冒泡排序的图解


  • 1.首先定义一个数组:int[] arr = {4,2,5,3,1}

  • 2.比较的图解是这样的:

1589944333585576.jpg

三、冒泡排序的思路解析

依次比较前后两个数的大小,如果后面的比前面的数小,那么直接将小的放在左边,大的数放在右边,以此类推

例如我们定义的数组: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往左边移动一位,5往后边移动一位,这样就把最大的数放到了最右边*现在通过比较并且移动之后,数组arr中的元素变成了{2,4,3,1,5}


第二圈比较:


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} *注意,现在第三圈比较的次数又少了一次


第四圈比较:


1.用arr[0]和arr[1]进行比较,那么2比1大,所以将1往左边移动一位,2往右边移动一位


*现在用过第四圈的比较,数组中的元素变成了{1,2,3,4,5},这样就比较完成了


那么通过这4圈的比较,可以确定我们数组的长度为5,但是我们比较了4次,所以我们可以确定,我们循环比较了4



所以,外层for循环可以确定为for(int i = 0,i<arr.length-1;i++).


每一圈比较的次数都会比上一圈的比较次数少1次,那么可以推断出来


a)进行第一圈元素比较时,内层循环次数为数组长度 - 1


b)进行第二圈元素比较时,内层循环次数为数组长度 - 2


c)依次类推,得出结论:进行第n圈元素比较时,内层循环次数为数组长度 - n


那么这个n的变化特点其实是跟外层for循环中的i是一致的,所以我们内存for循环可以确定为 for(int i = 0,i<arr.length-1-i;i++)


四、形成代码

//冒泡排序

public static void bubbleSort(int[] arr) {

//功能

//外层循环用来控制数组循环的圈数

for (int i = 0; i < arr.length-1; i++) {

//内层循环用来完成元素值比较,把大的元素值互换到后面

for (int j = 0; j < arr.length-1-i; j++) {

if (arr[j] > arr[j+1]) {

int temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

}

}

}

}

五、总结

以上是冒泡排序的具体思路分析,学习冒泡排序需要捋清楚其过程,主要是分析冒泡排序是怎么比较的。

 


收藏文章

分享

分享到:QQ空间新浪微博腾讯微博人人网微信
在线咨询 我要报名