java冒泡排序讲解

心已赠人 2023-03-01 13:47 7阅读 0赞

冒泡排序也是三种排序中较慢的一种  
选择排序，和快速排序为较快的两种排序  
下面来看下冒泡排序的原理

--------------------

原理：依次比较相邻两个数，大数往后，小数往前

--------------------

思路：  
依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。

第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较；

第二趟比较完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较；

依次类推，每一趟比较次数-1；

--------------------

**为了更好的演示，下面给出一种数组**

--------------------

假定我们有这样一种数组：

int a[]={ 5,0,2,14,8,7};

这是个无序数组，现在使用冒泡进行排序

## 第一趟 ##

#### 第一次排序 ####

第一个数5比0大，则5和0互换，数组变为

a[]={ 0,5,2,14,8,7};

#### 第二次排序 ####

第二个数5比2大，则5和2互换，数组变为

a[]={ 0,2,5,14,8,7};

#### 第三次排序 ####

第三个数5比14小，则不动，数组依然为

a[]={ 0,2,5,14,8,7};

#### 第四次排序 ####

第四个数14比8小，则14和8互换，数组为

a[]={ 0,2,5,8,14,7};

#### 第五次排序 ####

第五个数14比7大，则14和7互换，数组为

a[]={ 0,2,5,8,7,14};

第一趟结束，第二趟开始

# 第二趟 #

#### 第一次排序 ####

第一个数0比2小，不动

#### 第二次排序 ####

第二个数2比5小，不动

#### 第三次排序 ####

第三个数5比8小，不动

#### 第四次排序 ####

第四个数8比7大，互换，数组为

a[]={ 0,2,5,7,8,14};

第二趟结束

# 第三趟 #

三次排序后数组不动

# 第四趟 #

两次次排序后数组依然不动

# 第五趟 #

一次排序后数组依然不动

--------------------

五趟下来，数组终于变为有序数组了

# 代码 #

由此可见，N个数字想要排序完成，需要N-1趟排序，每次排序为N-i次，这种方法笨拙，使用双重for完成：

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

但他也并不是没有优点的，每次内循环结束就会减少一次排序  
时间复杂度为：O(n2)  
完整代码：

/** * 功能：演示冒泡排序方法 */
    package lesson_17;
    
    public class Bubble_sort { 
    
    	/** * @param args */
    	public static void main(String[] args){ 
    		// TODO 自动生成的方法存根
    		
    		int arr[]={ 1,6,0,-1,9,-100,90};
    		
    		//创建一个Bubble类
    		Bubble bubble =new Bubble();
    		bubble.sort(arr);
    	}
    }
    
    class Bubble
    { 
    	//排序方法
    	public void sort(int arr[])
    	{ 
    		int temp=0;
    		
    		//排序
    		//外层循环,它决定一共走几趟
    		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])
    				{ 
    					//换位
    					temp=arr[j];
    					arr[j]=arr[j+1];
    					arr[j+1]=temp;
    				}
    			}
    		}
    		
    		//输出最后的结果
    		for(int i=0;i<arr.length;i++)
    		{ 
    			System.out.print(arr[i]+" ");
    		}
    	}
    }

其他两种排序更新中……  
快速排序链接：[https://blog.csdn.net/weixin\_45445598/article/details/107608477][https_blog.csdn.net_weixin_45445598_article_details_107608477]  
选择排序链接：[https://blog.csdn.net/weixin\_45445598/article/details/107606792][https_blog.csdn.net_weixin_45445598_article_details_107606792]

[https_blog.csdn.net_weixin_45445598_article_details_107608477]: https://blog.csdn.net/weixin_45445598/article/details/107608477
[https_blog.csdn.net_weixin_45445598_article_details_107606792]: https://blog.csdn.net/weixin_45445598/article/details/107606792