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

一：概述

对于冒泡排序的优化1中，右边的许多元素已经是有序的了，可是每一轮还是白白地比较多次了。

这个问题地关键点在于对数列有序区地界定。

按照现有的逻辑，有序区的长度和排序的轮数是相等的。例如第1轮排序过后的有序区长度是1，第2轮排序过后的有序长度是2....

实际上，数列真正的有序区可能会大于这个长度，如上述例子中在第2轮排序时，后面的5个元素实际上已经都已经是有序区了。因此后面的多次元素比较有意义的。

那么，如何避免这种情况呢？我们可以在每一轮排序之后，记录下来最后一次元素交换的位置，该位置即无序数列的边界，再往后就是有序区了。

二：具体代码

 public static void sort2(int[] array) {
         // 记录最后一次交换的位置
         int lastExchangeIndex = 0;
         // 无序数列的边界，每次比较只需要比到这里为止
         int sortBorder = array.length - 1;
         for(int i = 0; i < array.length - 1; i++) 
         {
          // 有序标记，每一轮的初始值都是true
          boolean isSorted = true;
          for(int j = 0; j < sortBorder; 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;
                  // 更新为最后一次交换元素的位置
                  lastExchangeIndex = j;
              }
          }
             sortBorder = lastExchangeIndex;
             if (isSorted) {
                 break;
             }
         }
     }

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

在这个代码中，sortBorder就是无序数列的边界。在每一轮的循环排序过程中，处于BorderIndex之后的元素就不需要在进行比较了，肯定就是有序的。