java排序算法冒泡排序的优化

不念不忘少年蓝@ 2021-12-21 02:05 237阅读 0赞

### 冒泡排序的优化 ###

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

#### **1. 原理** ####

*  比较相邻的两个元素，如果第一个比第二个大就交换位置。
 *  对每一对相邻的元素进行比较，从开始第一队到结尾的最后一对，这样最后的元素就是最大的了。
 *  每一次这样循环一次之后都会有一个最大的数在后面，每确定一个最大的数，那个数在最后面不动它，这是内循环。
 *  每次循环确定最大得数沉到最底下，一共要循环数组的长度减一次，这是外循环。

![33a947c71ad62b254cab62e5364d28138293.gif][]

#### 2. 示例 ####

*  假如有这样一组数据int arr\[\] = \{2, 7, 6, 5, 9,10\};
    
        第一趟：2 6 5 7 9 10    7.6交换  7.5交换
        第二趟：2 5 6 7 9 10    6.5交换
        第三趟：2 5 6 7 9 10
        第四趟：2 5 6 7 9 10
        第五趟：2 5 6 7 9 10
    
    以上，其实第三次冒泡的时候，数组已经是有序的了，因此，还可以优化，即如果当次冒泡操作**没有数据交换时，那么就已经达到了有序状态**，不需要进行后面的循环判断操作，为了实现这个想法，新加一个flag变量来实现这一改进。
    
        * 改良后的冒泡排序
        	 * 
        	 * @param arr 需要排序的数组
        	 */
        	public void bubbleSort2(int[] arr) { 
        		int num = 0;//记录趟数
        		boolean flag = true;//标记位
        		//若flag为false 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素，这个数组就已经是有序的了.
        		for (int i = 0; i < arr.length - 1 && flag; i++) { 
        			flag = false;
        			num ++;
        			// 数组下标从0开始的，i下标后面已经排序的个数就得多减1，i增多少，j的循环位置减多少
        			for (int j = 0; j < arr.length - 1 - i; j++) {  	
        				if (arr[j] > arr[j + 1]) {  
        					swap(arr, j, j + 1);//交换arr[j]和arr[j+1]的值
        					flag = true;//发生了数据交换将flag设为true
        				
        				}
        			}
        		}
        		System.out.println("比较的趟数为："+num);
        	}

[33a947c71ad62b254cab62e5364d28138293.gif]: /images/20211221/21650d2344cc41f997d1028426043daf.png