入门算法：希尔排序

上手难度：★★★★

算法复杂度：O(n^(1.3—2))

shell.gif

排序思想：

最开始以整个数组长度的一半作为步长gap进行分组；
例如8个元素，索引0和索引4一组，索引1和索引5一组，索引2和索引6一组，索引3和索引7一组，分别对分好的组使用插入排序进行排序，这样就得到了4个已经排好序的四组数据，
再对步长gap进行对半取值得到2，就会将索引0、索引2、索引4和索引6一组，索引1、索引3、索引5和索引7一组，再对这两组进行插入排序，就得到了两个排好序的数组；
再对步长gap进行对半取值得到1，就得到了一组数据，再对这一组数据进行插入排序，就能得出最终结果；

之所以没有一开始就进行插入排序，是因为，在大量数据面前，希尔排序通过对一个个分组进行排序，减少了比较和交换需要的次数，下图是10000个元素下插入排序和希尔排序的对比

代码实现：

public class ShellSort {

    /**
     * 插入排序，以gap为分组，往前进行比较
     * 在gap为一半时，insert是每次对不同的分组进行操作
     * 当gap为四分之一时，在i的自增和循环过程中，insert会先以四分之一的步长对前面的一部分进行排序，         
     * 然后再通过步长找到后面的值加入到前面的分组中，例如索引0、索引2、索引4和索引6一组，会先将索引0和2排好序，然后将4加入到0和2的数组中进行排序，这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
     */
    private static void insert(int[] arr, int gap, int i){
        int temp = arr[i];
        //第一次进来i就等于gap的值，从gap开始往前比较
        int j;

        //插入的时候按组进行插入（组内元素两两相隔gap）
        //这里循环的次数根据gap的值来确定，第一个gap等于整个数组长度的一半，这里只能循环一次，后面gap会慢慢按2等比缩小，循环的次数也多了，gap越小，分到的组员就越多
        for(j = i - gap; j >= 0 && temp < arr[j]; j -= gap){
            //将两两相隔gap的值进行比较，如果前一个值大于temp，就把前面的值赋给后面的值
            //之所以把这个加入到判断条件，是因为按照插入排序的思维，默认前面已经排好序了
            // 事实也的确如此，因为最开始对半取到的gap，只会有两个值作为1组，然后排好这一组后，才会在i的自增中把后面的gap步长的值加入进来
            arr[j+gap] = arr[j];
        }

        arr[j+gap] = temp;
        //由于j已经自减了gap，此时j+gap是gap前面的值，等于是交换了元素位置，把小值换到前面了
    }

    private static void shellSort(int[] arr){
        int n = arr.length;
        //每次都对半取gap的值，以gap为步长进行分组
        for(int gap = n/2; gap > 0; gap /= 2){
            for(int i = gap; i < n; i++){
                //对各个分组进行插入排序 这里会循环n-gap次，每一次的循环，都是以gap为步长找到组员进行排序
                //这个循环的目的是以gap距离等比作为一组
                insert(arr, gap, i);
            }
        }
    }

    public static void main(String[] args) {

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        shellSort(arr);

        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }

    }
}

优点：

减少交换次数，比插入排序提高了效率，因为插入排序每次只比较一位，而希尔排序通过分组的形式，减少了比较次数

缺点：

反直觉，只适合计算机中使用

优化方式：

希尔排序的间隔序列不推荐用2的幂(1 2 4 8 16...)，因为这样直到间隔为1之前，
都不会将奇数位置与偶数位置的元素进行比较，这样是低效的。希尔自己认为可以用2的幂 - 1序列(1 3 7 15...)，后来又有文章建议用3x + 1(1 4 13 40 121...)，都是可以的。

    public static void shellSort2(int[] arr){
        int gap = 1;
        while (gap < arr.length/3) {
            gap = gap * 3 + 1;
        }
//        当gap小于数组整个长度的三分之一时，就自增3倍并且加1
//        1 4 13 40这种增长模式

        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                insert(arr, gap, i);
            }
            gap = (int) Math.floor(gap / 3);
        }
    }

最后编辑于：2020.09.01 16:13:33