希尔排序

选择排序和插入排序原理简单,希尔排序理解起来复杂一些
希尔排序是基于插入排序的。
先来想一下插入排序存在的问题:假如一个元素的初始位置离正确位置特别远,比如手里16张牌,最后摸了一张3,此时要想把它插入到最左边,根据插入排序算法,先与第16张牌比较并交换,最后要交换16次才能到第一位,每次移动一个位置的效率很低,希尔排序的思想主要就是改进这个问题。
希尔排序把元素分为有间隔(记为h)的组,首先通过插入排序使每一组中的元素是有序的
如下图,首先以h=5把数据分为5组,每组分别用插入排序法排序,此时得到黄色行的一个新数组,
再以h=2把数据分为两组,同样用插入排序排序,
最后h=1时,由于前两步数组中的元素已经非常有序了,此时再进行最后一次插入排序需要交换位置的元素已经非常少了
h的取值形成一个序列,一开始的值是非常大的,这样当元素交换时,移动的位置非常远,如图中的49和13,如果是传统的插入法,13需要每次一步的速度需要5步才能移到行首。

表格是用纯手工操作模拟了思路
这里写图片描述

    public void sort(Comparable[] arr) {
        int length = arr.length;
        //定义间隔数
        int h = 1;
//        while(h<length/3)
//            h = h*3+1;//1,4,13,40,121,364,1093,...,表达式可以自己定,+1是为了保证最后的间隔能成为1

        //这里使用一个自定义序列进行分组,也可以如上边注释的实时计算一个从1开始递增的数列
        int[] incr_arr = {1,2,5};
        for(int m=incr_arr.length-1;m>=0;m--){
            h = incr_arr[m];
            //外层循环根据分组数(length-h)来确定需要进行插入排序的次数
            for (int i = h; i < length; i++) {

                for (int j = i; j >= h; j -= h) {
                    if (less(arr[j], arr[j - h]))
                        exch(arr, j, j - h);
                }
            }
            System.out.println("间隔="+h+"分组时,整理后的数组="+ Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        Sort sort = new ShellSort();
        Integer[] arr = {49,38,65,97,76,13,27,49,55,4};
        sort.sort(arr);
        sort.show(arr);
    }

输出:

间隔=5分组时,整理后的数组=[13, 27, 49, 55, 4, 49, 38, 65, 97, 76]
间隔=2分组时,整理后的数组=[4, 27, 13, 49, 38, 55, 49, 65, 97, 76]
间隔=1分组时,整理后的数组=[4, 13, 27, 38, 49, 49, 55, 65, 76, 97]
[4, 13, 27, 38, 49, 49, 55, 65, 76, 97]

打印的三个数组对应表格中三个黄色行的时机。

决定h取值的序列如果能选好,效率会不一样,不过这个很难有好办法。
总之希尔排序法的速度非常快,对大型数组,任意排序的数组都是速度快的杠杠的。
数组越大,优势越大。
不需要使用额外的内存空间,代码量小。
虽然后边要学的更复杂的排序算法可能会更快,但是更复杂,有的也要用空间换时间。

原文链接:加载失败,请重新获取