希尔排序介绍

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

思路分析

假设待排序文件有10个记录，其关键字分别是：
8,9,1,7,2,3,5,4,6,0
在此我们选择增量gap=length/2,增量序列的取值依次为：
5,2,1

代码实现

public class ShellSort {
    public static void main(String[] args) {
        int[] array = {8,9,1,7,2,3,5,4,6,0};
        shellSort(array);
        //shellSort2(array);

    }

    /** *交换法 */
    public static void shellSort(int[] array){
        int temp = 0;
        int count =0;
        //这层for循环用来确定增量gap
        for (int gap=array.length/2;gap>0;gap=gap/2){
            count++;
            //从第gap个元素开始逐个对其所在组进行插入排序
            for (int i = gap;i<array.length;i++){
                //遍历各组中的元素,每组元素相隔gap个单位
                for (int j = i-gap;j >= 0;j-=gap){
                    if (array[j] > array[j+gap]){
                        temp = array[j];
                        array[j] = array[j+gap];
                        array[j+gap] = temp;
                    }
                }
            }
            System.out.println("第"+count+"轮希尔排序后的结果"+Arrays.toString(array));
        }
    }
    /** * 移动法 */
    public static void shellSort2(int[] array){
        int count =0;
        for (int gap = array.length/2;gap >0;gap=gap/2) {
            count++;
            for (int i = gap; i < array.length; i++) {
                //要插入的元素的下标
                int j = i;
                //要插入的元素
                int insert = array[j];
                if(array[j]<array[j-gap]){
                	//insert<array[j-gap]还没找到要插入的位置
                	while(j-gap>=0 && insert<array[j-gap]){
                    	//后移
                    	array[j] = array[j-gap];
                    	j -= gap;
                	}
                	//退出循环表示找到位置
                	array[j] = insert;
                }
            }
            System.out.println("第"+count+"轮希尔排序后的结果"+Arrays.toString(array));
        }
    }
}

运行结果

第1轮希尔排序后的结果[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
第2轮希尔排序后的结果[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
第3轮希尔排序后的结果[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Process finished with exit code 0

对比10万个数希尔排序和插入排序的效率

public class Test{
    public static void main(String[] args) {
		//创建两个长度为十万的数组
        int[] array1 = new int[100000];
        int[] array2 = new int[100000];
        for (int i = 0; i < 100000; i++) {
        	//随机生成10万个数字
            array1[i] =(int)(Math.random()*100000);
            array2[i] =(int)(Math.random()*100000);
        }
        //记录希尔排序开始时间
        long startTime = System.currentTimeMillis();
        shellSort2(array1);
        //记录希尔排序结束时间
        long endTiem = System.currentTimeMillis();
        System.out.println("希尔排序10万个数总共耗时"+(endTiem-startTime)+"ms");
        //记录插入排序开始时间
        long startTime1 = System.currentTimeMillis();
        insertSort(array2);
        记录插入排序结束时间
        long endTiem1 = System.currentTimeMillis();
        System.out.println("插入排序10万个数总共耗时"+(endTiem1-startTime1)+"ms");

    }

执行结果

希尔排序10万个数总共耗时16ms
插入排序10万个数总共耗时901ms

Process finished with exit code 0