希尔排序

1、希尔排序介绍
希尔排序也是一种插入排序，只不过它比插入排序要更高效。

2、基本思想

把记录按下标的一定分量进行分组，然后每组进行插入排序。随着增量越来越少，每组的数据就越来越多，当增量为1时，也就排好了序。

3、希尔排序示意图


4、代码示例

方法一：交换法

public class ShellSort1 {

    public static void main(String[] args) {
        int arr[] = new int[]{1, 5, 2, 6, 7, 4};
        shellSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    public static void shellSort(int[] arr) {

        int temp = 0;
        for(int gap = arr.length/2; gap >= 1; gap /= 2) {
            for(int i = gap; i < arr.length; i++) {
                for(int j = i - gap; j > 0; j -= gap) {
                    if(arr[j+gap] < arr[j]) {
                        temp = arr[j+gap];
                        arr[j+gap] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }
    }
}

方法二：移位法

 public static void shellSort2(int[] arr) {
        int temp = 0;
        for(int gap = arr.length/2; gap > 0; gap /= 2) {
            for(int i = gap; i < arr.length; i++) {
                int j = i;
                temp = arr[j];
                if(arr[j] < arr[j-gap]) {
                    while(j-gap >= 0 && temp < arr[j-gap]) {
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
        }
    }