java代码两种写法实现冒泡排序以及冒泡排序的优化

阳光穿透心脏的1/2处 2022-05-16 02:50 224阅读 0赞

冒泡排序重点在于对给定数字序列的逐对扫描以及交换，其写法并不唯一。一般情况下，外层循环表示扫描的轮数，内层循环表示需要扫描的元素个数。排在最前面的既可以是最大值，也可以是最小值；对给定数据可以顺序扫描，也可以进行逆序扫描，其结果是等效的。对此，我在这里提供了两种写法和一种优化方案与大家分享。

### 方案一：顺序扫描给定数据，将无序数列中的最大元素依次排到最后。即先冒出最大的气泡 ###

注释掉的代码部分提供了外层循环每轮冒泡结果的输出，以供各位参考。

/**顺序扫描给定数据，将无序数列中的最大元素依次排到最后。即先冒出最大的气泡*/
    	public static int[] BubbleSort1(int[] array){
    		int t = 1;
    		for(int i = 0 ; i < array.length - 1 ; i++){
    			for(int j = 0; j < array.length - 1 - i ; j++){
    				if(array[j] > array[j+1]){
    					t = array[j];
    					array[j] = array[j+1];
    					array[j+1] = t;
    				}
    			}
    //			for (int a : array) {
    //				System.out.print(a+" ");
    //			}
    //			System.out.println();
    		}
    		return array;
    	}

### 方案二：逆序扫描给定数据，将无序数列中的最小元素依次排到最前端。即先冒出最小的气泡 ###

/**逆序扫描给定数据，将无序数列中的最小元素依次排到最前端。即先冒出最小的气泡*/
    	public static int[] BubbleSort2(int[] array){
    		int t = 1;
    		for(int i = 0 ; i < array.length - 1 ; i++){
    			for(int j = array.length - 1 ; j > 0 ; j--){
    				if(array[j-1] > array[j]){
    					t = array[j];
    					array[j] = array[j-1];
    					array[j-1] = t;
    				}
    			}
    //			for (int a : array) {
    //				System.out.print(a+" ");
    //			}
    //			System.out.println();
    		}
    		return array;
    	}

### 方案三：优化方案(注释部分有介绍，这里就不加说明了) ###

/**对冒泡排序的优化：添加flag变量。初始值为0，若在某次外层循环中进行了交换，使flag = 1；
    	 * 在没有元素能够进行交换时，flag依然为0，即终止循环。
    	 * 这样的方式可以使得排序已经完毕时，可以提前终止循环，
    	 * 但作用不大，冒泡排序的效率并没有较大的提升。*/
    	public static int[] BubbleSort3(int[] array){
    		int t = 10;
    		int flag = 0;
    		for(int i = 0 ; i < array.length - 1 ; i++){
    			for(int j = array.length - 1 ; j > 0 ; j--){
    				if(array[j-1] > array[j]){
    					t = array[j];
    					array[j] = array[j-1];
    					array[j-1] = t;
    					flag = 1;//表示在此次外层循环中元素发生过交换
    				}
    			}
    			if(flag == 0){//表示在上次的扫描中，没有元素进行交换，此时数据已经排序完成
    				break;
    			}else{
    				flag = 0;
    			}
    //			for (int a : array) {
    //				System.out.print(a+" ");
    //			}
    //			System.out.println();
    		}
    		return array;
    	}

**这里还给出了main方法，方便各位测试使用**

public static void main(String[] args) {
    		int[] array = new int[]{55, 29, 1, 7, 5, 8, 88, 99, 100, 3};
    		array = BubbleSort1(array);
    		for (int i : array) {
    			System.out.println(i);
    		}
    	}

**冒牌排序的效率是比较低的，若不对其进行优化，它的逐对扫描方法所提供的效率无疑每次都是O(n²)的。**