结果

image.png

移位式完整代码（更好）

从gap位置依次往前比，小于则移位，最后把gap位置的数交换过去

package Sort;

/**
 * @author klr
 * @create 2020-07-07-19:16
 */
public class MoveShellSort {

    public static void main(String[] args) {

        MoveShellSort moveShellSort = new MoveShellSort();
        int[] array=new int[]{3,8,9,7,6,3,5,2,1,0};
        moveShellSort.moveSort(array);
        for (int i : array) {
            System.out.print(i+" ");
        }

    }

    public void moveSort(int[] array){
        boolean flag=false;
        for (int gap = array.length / 2; gap >0; gap /= 2) {
            for (int two = gap; two < array.length; two++) {
                int j=two;
                int temp=array[j];
                while (j - gap >= 0 && temp < array[j - gap]) {
                    flag=true;
                    //移动
                    array[j] = array[j - gap];
                    j -= gap;
                }
                //当退出while后，给temp找到插入的位置
                if(flag){
                    array[j] = temp;
                }
            }
        }
    }

    public void swapSort(int[] array){
        for(int gap=array.length/2;gap>0;gap/=2){
            //分组的第一个组的第二个数开始到最后，进行逆序的插入排序（感觉很像这个过程冒泡，不过确实是插入排序）
            //因为它是一个个插入到原有的数组进行比较交换，不是冒泡那种能一次定一个值
            //gap=5，相当于对5组，每组2个值进行插入排序
            //gap=2，相当于对2组，每组5个值进行插入排序
            //前两个处理完后，此时小数基本都排到前面了
            //gap=1，对10个数进行插入排序
            for (int two = gap; two < array.length; two++) {
                for (int first = two-gap; first >= 0; first -= gap) {
                    //大于则把小数往前交换
                    if (array[first] > array[first + gap]) {
                        int temp=array[first];
                        array[first] = array[first + gap];
                        array[first + gap] = temp;
                    }
                }
            }
            //打印每个gap后的数组
            System.out.println("gap:"+gap);
            for (int i : array) {
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }
}

交换式完整代码（过多的交换导致它效率更低）

倒数第二个数与gap位置的数比，gap位置的数小则两两交换，这也是交换式效率低的原因。交换的代价永远比移动大，因为它还要创建个辅助结点

package Sort;

/**
 * @author klr
 * @create 2020-07-06-22:31
 */
public class ShellSort {

    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        int[] array=new int[]{3,8,9,7,6,3,5,2,1,0};
        shellSort.sort(array);
    }

    public void sort(int[] array) {
        System.out.println("原数组：");
        for (int i : array) {
            System.out.print(i+" ");
        }
        System.out.println();
        for(int gap=array.length/2;gap>0;gap/=2){
            //分组的第一个组的第二个数开始到最后，进行逆序的排序（感觉很像这个过程冒泡）
            //因为它是一个个插入到原有的数组进行比较交换，不是冒泡那种能一次定一个值
            //gap=5，相当于对5组，每组2个值进行插入排序
            //gap=2，相当于对2组，每组5个值进行插入排序
            //前两个处理完后，此时小数基本都排到前面了
            //gap=1，对10个数进行插入排序
            for (int two = gap; two < array.length; two++) {
                for (int first = two-gap; first >= 0; first -= gap) {
                    //大于则把小数往前交换
                    if (array[first] > array[first + gap]) {
                        int temp=array[first];
                        array[first] = array[first + gap];
                        array[first + gap] = temp;
                    }
                }
            }
            //打印每个gap后的数组
            System.out.println("gap:"+gap);
            for (int i : array) {
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }

}