冒泡排序的详细过程

小鱼儿 2024-03-27 14:41 84阅读 0赞

###  **简介** ###

冒泡排序的核心实现思路，就是把数据元素按照从下到上，两两进行比较。所以冒泡排序的特点是，每一轮循环后，最大的一个数被交换到末尾。因此，下一轮循环可以“刨除”最后的数，每一轮循环都比上一轮循环的结束位置靠前一位。冒泡排序整体可以分为两种情况，即升序排列和降序排列。

**升序排列的实现思想：**

1. 将数组中相邻的两个数据元素进行比较，如果前面一个元素比后面的大，就把两者交换位置(一轮比较)；

2. 然后将上面的操作进行循环(比较n-1轮)。

排列过程如下图所示：

![16e0b8632cd94833bd7cca1debbe0e66.png][]

**降序排列的实现思想：**

1. 将数组中相邻的两个数据元素进行比较，如果前面一个元素比后面的小，就把两者交换位置(一轮比较)；

2. 然后将上面的操作进行循环(比较n-1轮)。

###  **基本实现** ###

大家要注意，面试时经常会让我们手写冒泡排序和选择排序等算法，你必须牢牢地记住相关的代码实现哦。

public class Demo09 {
    
    	public static void main(String[] args) {
    		// 冒泡排序--基本实现
    
    		//待排序的数组
    		int[] arr = { 1, 3, 46, 22, 11 };
    
    		//控制需要比较几轮
    		for (int i = 0; i < arr.length; i++) {
    			//控制每一轮的比较次数
    			for (int j = 0; j < arr.length - 1; j++) {
    				//如果前面的比后面的数字大，则两者就进行交换
    				if (arr[j] > arr[j + 1]) {
    					//两数交换，需要一个“第三方”，好比两杯水互换，需要第三个杯子。
    
                        //交换两个变量的值，必须借助一个临时变量。
    					//定义一个新的临时变量，将数组中的前面的元素先赋值给临时变量
    					int 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]+"\t");
    		}
    	}
    }

这种实现方式比较容易理解，但并不是最优的实现方案，因为这种方案需要比较的次数较多。我们可以进一步对该方案进行优化，将比较的次数降下来，请继续往下看。

### **优化次数** ###

在本案例中，会对比较次数进行优化。

public class Demo10 {
    
    	public static void main(String[] args) {
    		// 冒泡排序--优化比较次数
            
    		// 待排序数组
    		int[] arr = { 1, 3, 46, 22, 11 };
    
    		for (int j = 0; j < arr.length; j++) {   //控制轮数
    	        for (int i = 0; i < arr.length - 1 - j; i++) {//控制每一轮的次数
    	            if(arr[i] > arr[i+1]) {
    	                int temp = arr[i];
    	                arr[i] = arr[i+1];
    	                arr[i+1] = temp;
    	            }
    	        }
    	    }
    		
    		//遍历排序后的数组
    		for(int i=0;i<arr.length;i++) {
    			System.out.print(arr[i]+"\t");
    		}
    	}
    
    }

本案例同样也不是最优的实现方案，我们也可以对该实现方案进行优化。

### **优化轮数** ###

在本案例中，小千会对比较的轮数进行优化。

public class Demo11 {
    
    	public static void main(String[] args) {
    		// 冒泡排序--优化比较轮数
    
    		// 待排序数组
    		int[] arr = { 1, 3, 46, 22, 11 };
    
    		for (int j = 0; j < arr.length - 1; j++) { //轮数
    	        //假设这一轮已经拍好序，设置一个标签进行记录
    	        boolean flag = true;
    	        
    	        for (int i = 0; i < arr.length - 1 - j; i++) {//每一轮比较的次数
    	            if(arr[i] > arr[i+1]) {
    	            	//更改是否比较过的标签
    	                flag = false;
    	                int temp = arr[i];
    	                arr[i] = arr[i+1];
    	                arr[i+1] = temp;
    	            }
    	        }
    	        
    	        //如果本轮已排序好，则直接跳过，避免没必要的比较。
    	        if(flag) {
    	            break;
    	        }
    	    }
    		
    		//遍历排序后的数组
    		for(int i=0;i<arr.length;i++) {
    			System.out.print(arr[i]+"\t");
    		}
    	}
    }

这种实现方案，可以说是三种方案中最优的一种，但对初学者来说，理解起来确实不容易。但是**壹哥都会针对每一个步骤进行详细的讲解的，**不用怕自己理解不了。

[16e0b8632cd94833bd7cca1debbe0e66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/361f7db46a1d47e4bcbb7e4d85bd1bcc.png