排序算法之冒泡排序优化1

一：概述

原始的数列{4， 8， 6， 3， 9，2，1， 7}，执行至第6步和第7步时，数列状态如下：

很明显的可以看出，经过第6轮排序之后，整个数列已然是有序的了。可是排序算法依然是继续执行第7轮排序。

在这种情况下，如果能判断出数列已经有序，并作出标记，那么剩下的几轮就不必执行了，可以提前结束。

二：具体代码

优化的代码如下：

 public static void sort(int[] array)
     {
       for(int i = 0; i < array.length -1; i++) {

           // 有序标记,每一轮的初始值都是true
           boolean isSorted = true;
           for(int j = 0; j < array.length - i - 1; j++) {
               int tmp = 0;
               if(array[j] > array[j + 1]) {
                   tmp = array[j];
                   array[j] = array[j + 1];
                   array[j + 1] = tmp;
                  // 因为有元素进行交换，所以不是有序的，标记变为false
                  isSorted = false;
               }
           }
           if(isSorted) {
               break;
           }
       }
     }




public static void main(String[] args) {
         // 定义数组
         int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
         // 调用冒泡排序的方法
         sort(array);
         System.out.println(Arrays.toString(array));
     }

与第一版的代码相比，第二版的代码做了小小的改动，利用布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明无序；如果没有元素交换，则说明数列已然有序，然后直接跳出大循环。

下面以一个新的数列为例说明。

这个数列的特点就是前半部分的元素(3、4、2、1)无序，后半部分的元素(5、6、7、8)按升序排列，并且后半部分元素中的最小值也大于前半部分元素的最大值。

下面按照冒泡排序的思路进行排序，看看效果：

第一轮

元素4和5比较，发现4小于5，所以位置不变。

元素5和6比较，发现5小于5，所以位置不变。

元素6和7比较，发现6小于7，所以位置不变。

元素7和8比较，发现7小于8，所以位置不变。

第1轮结束，数列有序区包含1个元素。

第二轮

元素3和2比较，发现3大于2，所以3和2交换。

元素3和4比较，发现3小于4，所以位置不变。

元素4和5比较，发现4小于5，所以位置不变。

元素5和6比较，发现5小于6，所以位置不变。

元素6和7比较，发现6小于7，所以位置不变。

元素7和8比较，发现7小于8，所以位置不变。

第2轮结束，数列有序区包含两个元素。