• 第i轮开始，arr[n-i, n)已排好序
    • 第i轮: 通过冒泡在arr[n-i- 1]位置放上合适的元素
    • 第i轮结束:arr[n-i- 1, n)已排好序
    1.     private static <E extends Comparable<E>> void sort3(E[] data) {
    2.         for (int i = 0; i < data.length - 1;) {
    3.             int lastSwappedIndex = 0;
    4.             for (int j = 0; j < data.length - i - 1; j++) {
    5.                 if (data[j].compareTo(data[j + 1]) > 0) {
    6.                     swap(data, j, j + 1);
    7.                     lastSwappedIndex = j + 1;
    8.                 }
    9.             }
    10.             //arr[n - i, n)已排好序
    11.             i = data.length-lastSwappedIndex;
    12.         }
    13.     }