3.4、希尔排序(Shell's Sort)

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

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

3.4.3、API设计

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毫秒

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