排序----希尔排序

佚名 6年前 (2019-04-21) 随笔 672人围观抢沙发百度已收录

一.原理

　　1.1.动态演示图

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　1.2.动态图讲解

　　希尔排序是设置一个步长，比如步长为2,0 2 4 6..,1 3 5...就分为了两组对步长为2进行插入排序，排序完后将步长除以2在进行插入排序，直至步长为零，此时数组即有序.

　　1.3.数据演示

　　原始数组：8 4 7 10 6 5 4 8

　　初始步长：数组长度/2 本案例为4

　　对下标分别为0 4,1 5,2 6,3 7四组数据进行排序

　　6 4 4 8 8 5 7 10

　　将步长/2进行上述操作直至步长为0结束

二.代码实现

public class ArraySortUtils {

    /**
     * 返回数组的字符串
     * @param array
     * @return
     */
    public static String arrayToString(int[] array){
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < array.length; i++) {
            if( i != (array.length - 1)){
                sb.append(array[i] + ",");
            }else{
                sb.append(array[i] + "]");
            }
        }
        return sb.toString();
    }


    /**
     * 希尔排序
     * @param array
     */
    public static void shellSort(int[] array){
        //设置步长，并开始以当前步长进行排序，每次排序完将步长/2，直至步长为0退出
        for(int d = array.length/2; d > 0; d /= 2){
            //对步长相同的组进行插入排序
            for(int i = d; i < array.length ; i++){
                for(int j = i - d; j >= 0; j -= d){
                    if(array[j + d] < array[j]){
                        int temp = array[j + d];
                        array[j + d] = array[j];
                        array[j] = temp;
                    }
                }
            }
            System.out.println("步长为" + d + "时排序结果：" + arrayToString(array));
        }
    }
}

三.演示结果

public class ArraySortUtilsDemo {

    public static void main(String[] args) {
        //6 4 4 8 8 5 7 10
        int[] array = new int[]{8,4,7,10,6,5,4,8};
        System.out.println("排序前：" + ArraySortUtils.arrayToString(array));
        //ArraySortUtils.bubbleSort(array);
        //ArraySortUtils.quickSort(array);
        //ArraySortUtils.insertSort(array);
        ArraySortUtils.shellSort(array);
        System.out.println("排序后：" + ArraySortUtils.arrayToString(array));
    }
}