八大排序之交换排序—冒泡排序

拼搏现实的明天。 2022-05-13 03:40 230阅读 0赞

## 冒泡排序 ##

最简单排序实现  
可以做成参考：[https://www.cnblogs.com/shen-hua/p/5422676.html][https_www.cnblogs.com_shen-hua_p_5422676.html]  
冒泡排序的思想其实很简单，它是一种简单的选择排序，在细节上有很多种优化的方法。  
它的基本思想是：两两比较相邻记录的关键字，如果反序则进行交换。

冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。

原理：比较两个相邻的元素，将值大的元素交换至右端。  
思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。  
第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较；  
第二趟比较完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较；  
依次类推，每一趟比较次数-1；  
……

用时间复杂度来说：  
　　1.如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。  
　　2.如果很不幸我们的数据是反序的，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

冒泡排序的最坏时间复杂度为：O(n2) 。  
综上所述：冒泡排序总的平均时间复杂度为：O(n2) 。

代码：

public class Bubble {
    	public static void main(String[] args) {
    		int[] arr = {12,123,15,21,42,0,543,65};
    		Bubble b = new Bubble();
    		b.bubble(arr);
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i]+" ");
    		}
    	}
    	
    	//冒泡排序初级版
    	public void bubble(int[] arr){
    		//从下标为0的第一个元素与后面的每一个元素进行比较
    		for (int i = 0; i < arr.length-1; i++) {
    			for (int j = i+1; j < arr.length; j++) {
    				if (arr[i] > arr[j]) {
    					int temp = arr[i];
    					arr[i] = arr[j];
    					arr[j] = temp;
    				}
    			}
    		}
    	}
    }

这个初级版的冒泡排序不算是真正意义上的冒泡排序，它的思路是让每一个数字都和它后面的数字进行比较。  
真正的冒泡排序  
代码1：

import java.util.*;
    
     //没有优化的方法，比较常规的冒泡排序
    public class Main {
    	public static void main(String[] args) {
    		@SuppressWarnings("resource")
    		Scanner sc = new Scanner(System.in);
    		String[] st = sc.nextLine().split(",");
    		int[] arr = new int[st.length];
    		for (int i = 0; i < st.length; i++) {
    			arr[i] = Integer.parseInt(st[i]);
    		}
    		bubble(arr);
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i]+" ");
    		}
    	}
    
    	public static void bubble(int[] arr) {
    		//外层循环控制排序趟数
    		for (int i = 0; i < arr.length - 1; i++) {
    			//内层循环控制每一趟排序多少次
    			for (int j = 0; j < arr.length-i-1; j++) {
    				if (arr[j] > arr[j+1]) {
    					int temp = arr[j];
    					arr[j] = arr[j+1];
    					arr[j+1] = temp;
    				}
    			}
    		}
    	}
    }

优化1：略微的优化方案BubbleSort2: 如果原数组就是有序的 比如： 1，2，3，4；  
如果我们继续按照BubbleSort1的方法，那还是要跑n-1趟，是不是有点浪费时间，  
于是，我们就想到了一个方法，没跑完一趟就判断一次原数组现在是否有序，如果有序；  
直接return 掉；于是这里就有了一个标志位flag去帮助我们判断！  
代码2：

import java.util.*;
    
    public class Main {
    	public static void main(String[] args) {
    		@SuppressWarnings("resource")
    		Scanner sc = new Scanner(System.in);
    		String[] st = sc.nextLine().split(",");
    		int[] arr = new int[st.length];
    		for (int i = 0; i < st.length; i++) {
    			arr[i] = Integer.parseInt(st[i]);
    		}
    		bubble(arr);
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}
    	}
    
    	// 添加标志位的冒泡排序
    	public static void bubble(int[] arr) {
    		if (arr.length == 0) {
    			System.out.println("输入不能为空");
    		} else {
    			// 加入标志位优化
    			for (int i = 0; i < arr.length - 1; i++) {
    				int flag = 1;// 假定每次进入都是有序的 flag为1
    				for (int j = 0; j < arr.length - i - 1; j++) {
    					if (arr[j] > arr[j + 1]) {
    						int temp = arr[j];
    						arr[j] = arr[j + 1];
    						arr[j + 1] = temp;
    						flag = 0;// 如果发生交换，则flag置为0
    					}
    				}
    				if (flag == 1) {
    					break;// 如果这趟走完，没有发生交换，则原数组有序
    				}
    			}
    		}
    	}
    }

优化2：减少内部循环比较的次数  
代码3：  
//最终优化

public class CopyOfBubbleTest1 {
    	public static void main(String[] args) {
    		int[] arr = {12,123,0,15,21,42,0,543};
    		CopyOfBubbleTest1 bt = new CopyOfBubbleTest1();
    		bt.bubble(arr);
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i]+" ");
    		}
    	}
    	
    	//添加标志位的冒泡排序
    	public void bubble(int[] arr){
    		int k = arr.length - 1;//控制内部比较循环
    		//加入标志位优化
    		for (int i = 0; i < arr.length-1; i++) {
    			int flag = 1;//假定每次进入都是有序的 flag为1
    			int n = 0;
    			for (int j = 0; j < k; j++) {
    				if (arr[j] > arr[j+1]) {
    					int temp = arr[j];
    					arr[j] = arr[j+1];
    					arr[j+1] = temp;
    					flag = 0;//如果发生交换，则flag置为0
    					n = j;//保存最后一次交换的下标
    				}
    			}
    			if(flag == 1){
    				break;//如果这趟走完，没有发生交换，则原数组有序
    			}
    			k = n;//最后一次交换的位置给k，减少比较的次数
    		}
    	}
    }

[https_www.cnblogs.com_shen-hua_p_5422676.html]: https://www.cnblogs.com/shen-hua/p/5422676.html