希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本。

3.4.1、需求

  • 排序前:{9, 1, 2, 5, 7, 4, 8, 6, 3, 5}
  • 排序后:{1, 2, 3, 4, 5, 5, 6, 7, 8, 9}

3.4.2、排序原理

  • 选定一个增长量h,按照增长量h作为数组分组的依据,对数据进行分组
  • 对分好组的每一组数据完成插入排序
  • 减少增长量,最小减为1,重复第二步操作

增长量h的选取:

int h = 1;//默认为1
while(h<数组的长度/2){
    h = 2 * h + 1;
}

#缩小增量,为h/2

图片alt

3.4.3、API设计

类名 Shell
构造方法 Shell:创建Shell对象
成员方法 public static void sort(Comparable[] a):对数组内的元素进行排序
private static boolean grater(Comparable v,Comparable w):判断v是否大于w
private static void exch(Comparable[] a,int i,int j):交换a数组中,索引i和索引j处的值

3.4.4、代码实现

算法类:

package cn.test.algorithm.sort;

public class Shell {
    /**
     * 对数组元素进行排序
     *
     * @param a
     */
    public static void sort(Comparable[] a) {
        //根据数组的长度确定增长量h的初始值
        int h = 1;
        while (h < a.length / 2) {
            h = 2 * h + 1;
        }
        //进行排序
        while (h >= 1) {
            for (int i = h; i < a.length; i++) {
                for (int j = i; j >= h; j -= h) {
                    if (greater(a[j - h], a[j])) {
                        exch(a, j - h, j);
                    } else {
                        break;
                    }
                }
            }

            //减小h的
            h = h / 2;
        }
    }

    /**
     * 比较v元素是否大于w元素
     *
     * @return
     */
    private static boolean greater(Comparable v, Comparable w) {
        return v.compareTo(w) > 0;
    }

    /**
     * 交换i和j处的元素值
     *
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

测试类:

package cn.test.algorithm.test;

import cn.test.algorithm.sort.Shell;

import java.util.Arrays;

public class TestShell {
    public static void main(String[] args) {
        Integer[] a = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};

        Shell.sort(a);

        System.out.println(Arrays.toString(a));
    }
}

测试结果:

[1, 2, 3, 4, 5, 5, 6, 7, 8, 9]

3.4.5、时间复杂度分析

由于希尔排序的时间复杂度事前预估法比较难,所以我们采用事后预估法,这里我们通过希尔排序和插入排序进行对比,看看希尔排序的执行时间。

package cn.test.algorithm.test;

import cn.test.algorithm.sort.Insertion;
import cn.test.algorithm.sort.Shell;


public class SortCompare {
    public static void main(String[] args) {
        //生成10w个证书,数据必须是倒序的,这样才是排序的最坏情况
        int num = 100000;
        //这里分开写两个数组
        Integer[] shellArray = new Integer[num];//希尔排序数组
        Integer[] insertionArray = new Integer[num];//插入排序数组
        for (int i = num; i > 0; i--) {
            shellArray[num - i] = i;
            insertionArray[num - i] = i;
        }
        shellTest(shellArray);
        insertionTest(insertionArray);
    }

    //希尔排序测试
    public static void shellTest(Integer[] a) {
        long startTime = System.currentTimeMillis();
        Shell.sort(a);
        long endTime = System.currentTimeMillis();

        System.out.println("希尔排序时间:" + (endTime - startTime) + "毫秒");
    }

    //插入排序测试
    public static void insertionTest(Integer[] a) {
        long startTime = System.currentTimeMillis();
        Insertion.sort(a);
        long endTime = System.currentTimeMillis();

        System.out.println("插入排序时间:" + (endTime - startTime) + "毫秒");
    }

}

运行结果:

希尔排序时间:24毫秒
插入排序时间:20380毫秒

从结果可以看出,希尔排序的效率是非常高的。