java冒泡排序详解

拼搏现实的明天。 2021-09-27 22:46 301阅读 0赞

**原理：比较两个相邻的元素，将值大的元素交换至右端。(按照从小到大顺序排列)**

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

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

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

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

**……**

定义任意数组：int\[\] arr = \{4,2,8,7,6,1,12,9\};

第1趟  
    第1次排序,4大于2    交换位置：4    2    8    7    6    1    12    9      
    第2次排序,4小于8不交换位置：2    4    8    7    6    1    12    9      
    第3次排序,8大于7    交换位置：2    4    8    7    6    1    12    9      
    第4次排序,8大于6    交换位置：2    4    7    8    6    1    12    9      
    第5次排序,8大于1    交换位置：2    4    7    6    8    1    12    9      
    第6次排序,8小于12不交换位置：2    4    7    6    1    8    12    9      
    第7次排序,12大于9    交换位置：2    4    7    6    1    8    12    9      
=============第1趟排序结果：2    4    7    6    1    8    9    12    =============

第2趟  
    第1次排序,2小于4不交换位置：2    4    7    6    1    8    9    12      
    第2次排序,4小于7不交换位置：2    4    7    6    1    8    9    12      
    第3次排序,7大于6    交换位置：2    4    7    6    1    8    9    12      
    第4次排序,7大于1    交换位置：2    4    6    7    1    8    9    12      
    第5次排序,7小于8不交换位置：2    4    6    1    7    8    9    12      
    第6次排序,8小于9不交换位置：2    4    6    1    7    8    9    12      
=============第2趟排序结果：2    4    6    1    7    8    9    12    =============

第3趟  
    第1次排序,2小于4不交换位置：2    4    6    1    7    8    9    12      
    第2次排序,4小于6不交换位置：2    4    6    1    7    8    9    12      
    第3次排序,6大于1    交换位置：2    4    6    1    7    8    9    12      
    第4次排序,6小于7不交换位置：2    4    1    6    7    8    9    12      
    第5次排序,7小于8不交换位置：2    4    1    6    7    8    9    12      
=============第3趟排序结果：2    4    1    6    7    8    9    12    =============

第4趟  
    第1次排序,2小于4不交换位置：2    4    1    6    7    8    9    12      
    第2次排序,4大于1    交换位置：2    4    1    6    7    8    9    12      
    第3次排序,4小于6不交换位置：2    1    4    6    7    8    9    12      
    第4次排序,6小于7不交换位置：2    1    4    6    7    8    9    12      
=============第4趟排序结果：2    1    4    6    7    8    9    12    =============

第5趟  
    第1次排序,2大于1    交换位置：2    1    4    6    7    8    9    12      
    第2次排序,2小于4不交换位置：1    2    4    6    7    8    9    12      
    第3次排序,4小于6不交换位置：1    2    4    6    7    8    9    12      
=============第5趟排序结果：1    2    4    6    7    8    9    12    =============

第6趟  
    第1次排序,1小于2不交换位置：1    2    4    6    7    8    9    12      
    第2次排序,2小于4不交换位置：1    2    4    6    7    8    9    12      
=============第6趟排序结果：1    2    4    6    7    8    9    12    =============

第7趟  
    第1次排序,1小于2不交换位置：1    2    4    6    7    8    9    12      
=============第7趟排序结果：1    2    4    6    7    8    9    12    =============

第8趟  
=============第8趟排序结果：1    2    4    6    7    8    9    12    =============

代码如下：

int[] arr = {4,2,8,7,6,1,12,9};
    		for (int i = 0; i < arr.length; i++) {
    			for (int j = 0; j < arr.length-1-i; j++) {
    				if(arr[j] > arr[j+1]){
    					int temp = arr[j+1];
    					arr[j+1] = arr[j];
    					arr[j] = temp;
    				}
    			}
    		}
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i]+"\t");
    		}

可以看到最终结果：已按照要求从小到大排序出来了，但是注意观察一下，发现后面有好几趟排序基本上没发生什么变化，主要是因为前面几趟已经把结果排出来，下面可以做一些优化，第6趟已经已经排出结果了，第7、8趟已不需要了，修改后的输出：

第6趟  
    第1次排序,1小于2不交换位置：1    2    4    6    7    8    9    12      
    第2次排序,2小于4不交换位置：1    2    4    6    7    8    9    12      
=============第6趟排序结果：1    2    4    6    7    8    9    12    =============  
  
**修改后的代码：**

int[] arr = {4,2,8,7,6,1,12,9};
    		for (int i = 0; i < arr.length; i++) {
    			boolean isChange = false;
    			for (int j = 0; j < arr.length-1-i; j++) {
    				if(arr[j] > arr[j+1]){
    					int temp = arr[j+1];
    					arr[j+1] = arr[j];
    					arr[j] = temp;
    					isChange = true;
    				}
    			}
    			if(!isChange){
    				break;
    			}
    		}
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i]+"\t");
    		}