2. //对交换式的希尔排序进行优化->移位法
  3. public static void shellSort2(int[] arr) {
  5.     // 增量gap, 并逐步的缩小增量
  6.     for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  7.         // 从第gap个元素，逐个对其所在的组进行直接插入排序
  8.         for (int i = gap; i < arr.length; i++) {
  9.             int j = i;
  10.             int temp = arr[j];
  11.             if (arr[j] < arr[j - gap]) {
  12.                 while (j - gap >= 0 && temp < arr[j - gap]) {
  13.                     //移动
  14.                     arr[j] = arr[j-gap];
  15.                     j -= gap;
  16.                 }
  17.                 //当退出while后，就给temp找到插入的位置
  18.                 arr[j] = temp;
  19.             }
  21.         }
  22.     }
  23. }

交换法中，每次排序都存在交换两个逆序数据的行为。如[5,6,8,4]其中元素4要交换到前面需要先和元素8交换，再和元素6交换，最后和元素5交换，更换到最前面。
假设有大量数据，而最后一个数据为最小数据，因此要交换至最前面，那么就需要和每一个数据交换，会产生大量运算。而移位法不需要。

若最后有一个小数,交换法,要循环比较,并挨个交换,直到交换到最前面

而移位法,直接找到前面的位置,并将其他数字都往后面移位

移位用了一层循环中的操作就实现了,交换不仅要循环一次,还要交换n次

希尔NB

就是这么效率
算法的魅力!!!