希尔排序 移动法

//对交换式的希尔排序进行优化->移位法
public static void shellSort2(int[] arr) {

    // 增量gap, 并逐步的缩小增量
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 从第gap个元素，逐个对其所在的组进行直接插入排序
        for (int i = gap; i < arr.length; i++) {
            int j = i;
            int temp = arr[j];
            if (arr[j] < arr[j - gap]) {
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    //移动
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                //当退出while后，就给temp找到插入的位置
                arr[j] = temp;
            }

        }
    }
}

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

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

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

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

希尔NB

就是这么效率

算法的魅力!!!