针对基本有序数列的改良冒泡排序

我把这个排序称为OooooSort

hahahaha虽然没有Java自带的TimSort高效，但也只是稍稍逊色，这是一个闲暇时做的小玩意~可以叫做双向冒泡法，或者改良冒泡法。

/**
 * 双向冒泡，不需要额外存储空间，速度稍慢于tim sort
 * @author zrj CreateDate: 2019/8/4
 */
public class OooooSort {

  public static <E> void sort(ArrayList<E> list, Comparator<E> comparator) {
    if(list == null || list.size() == 0) {
      return;
    }

    int maxSorted = 0;
    boolean hasSwap;
    E last;
    int j = 0;
    do {
      hasSwap = false;
      last = list.get(maxSorted);
      for(int i = 1; i < list.size() - j; i ++ ){
        E cur = list.get(i);
        if(comparator.compare(last, cur) > 0) {
          hasSwap = true;
          list.set(i - 1, cur);
          list.set(i, last);
          E innerLast = list.get(i - 1);
          for(int k = i - 2; k >=0; k--) {
            E innerCur = list.get(k);
            if(comparator.compare(innerCur, innerLast) > 0) {
              list.set(k + 1, innerCur);
              list.set(k, innerLast);
            } else {
              break;
            }
          }
        } else {
          if(!hasSwap) {
            maxSorted = i;
          }
          last = cur;
        }
      }
      j++;
    } while (maxSorted < list.size() && hasSwap);
  }
}

对于基本有序的数列，快排的效率是非常低的，相对来说，冒泡的潜力要更高一些，但是冒泡做了很多无用的工作，所以我稍稍改进了一下，每次冒一次泡后，都回头对刚刚换下去的数据进行一下反向冒泡（沉底），这样，每次向上冒一次泡之后，身后的数据都已经是全局有序的了，还有一个优化点，冒泡的时候可以记录下最长未发生交换的位置，应为没有发生过交换，所以这批数据是已经有序的，上面的代码中maxSorted就是用来干这个的，这样下轮冒泡就减少了很多工作。

如果数据基本有序，效率可以逼近O（n），突破排序的算法理论极限了有木有，好了当然不是，算法理论极限是通用情况，这里是基本有序。

但是Java提供的TimSort性能更加优秀。