Java教程

初识希尔排序

本文主要是介绍初识希尔排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

插入排序存在的效率问题
如果已经排序的分组元素为{2,5，7,9，10}未排序的分组元素为{1,8}那么下一个待插入元素为1，我们需要拿着1从后往前，一次和10,9，7,5，2进行位置交换，才能真正完成插入。如果我们要提高效率，就是把1放到更前面的位置，例如直接将1放到2前面，这样可减少交换次数。下面我们来看看希尔排序

将数组{9,1,2,57,4,8,6,3,5}正序

希尔排序原理
1、选定一个增长量，按照增长量h作为数组分组的依据，对数据进行分组
2、对分好组的每一组数据完成插入排序
3、减小增长量，最小减为1，重复第二部操作
在这里插入图片描述
第一次h应该为7，这里为了方便的分析排序过程，暂时写作5

增长量h的确定：增长量h的值固定规则如下

int h=1;
while(h<数组长度/2){
h=2h+1
}

增长量减少规则
h=h/2 如果除不开按照java的除法规则，例如7/2=3

代码

    public static void main(String[] args) {
        Integer arr[] = {9,1,2,57,4,8,6,3,5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
        sort(arr, Comparator.reverseOrder());
        System.out.println(Arrays.toString(arr));
    }


        /**
     * 自定义排序
     *
     * @param arr
     * @param comparator
     * @param <T>
     */
    public static <T> void sort(T[] arr, Comparator<T> comparator) {
        int h=1;
        while (h<arr.length/2) {
            h = 2 * h + 1;
        }
        while (h>=1){
            for (int i = h; i <= arr.length-1; i+=h) {

                for (int j = i; j >=h; j-=h) {
                    if(greater(comparator,arr[j],arr[j-h])){
                        exch(arr,j-h,j);
                    }else {
                        break;
                    }
                }
            }
            h=h/2;
        }

    }


    /**
     * 正序
     *
     * @param arr
     * @param <T>
     */
    public static <T> void sort(Comparable<T>[] arr) {
        //找到最大增量
       int h=1;
       while (h<arr.length/2) {
           h = 2 * h + 1;
       }
       //当增量为1的时候所有数据都在一组
       while (h>=1){
           //找到待排序元素，通过观察发现待排序元素的索引=增长量 所以i=h
           //arr.length-1 参与排序的最大索引 i+=h 因为待排序索引的开始值
           for (int  i= h; i <= arr.length-1; i+=h) {
               //假如h=2 待排序索引为8，通过已排好序的数组的索引6,4,2,0，发现每次都-h,
               //所以j=j-h,j>=h是因为0索引在if判断和位置交换的j-h索引处，否则会出现负数角标
               //j=i 因为待排序的索引是变化的，而这种变化是通过i体现出来的
               for (int j = i; j >=h; j-=h) {
                   if(greater(arr[j-h],arr[j])){
                       exch(arr,j,j-h);
                   }else {
                       break;
                   }
               }
           }
           h=h/2;
       }
       
    }

    /**
     * 比较大小，如果c1比c2大，返回true,否则false，正序
     *
     * @param c1
     * @param c2
     * @return
     */
    private static boolean greater(Comparable c1, Comparable c2) {
        return c1.compareTo(c2) > 0 ? Boolean.TRUE : Boolean.FALSE;
    }

    private static <T> boolean greater(Comparator comparator, T c1, T c2) {
        return comparator.compare(c1,c2 ) > 0 ? Boolean.TRUE : Boolean.FALSE;
    }

    /**
     * 将arr数组中i角标和j角标位置互换
     *
     * @param arr 数组
     * @param i   角标
     * @param j   角标
     * @param <T>
     */
    private static <T> void exch(T[] arr, int i, int j) {
        T temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

时间复杂度分析
在希尔排序中，增长量h并没固定的规则，很多论文中研究了不同的递增序列，但都无法证明某个序列是最好的，对于希尔排序的时间复杂度分析，设计很多数学知识，这里不做分析了。
所以我们采用事后分析法对希尔排序和插入排序的性能做比较

希尔排序最坏情况事后分析法

public class Shell {

    public static void main(String[] args) {
        Integer arr[] = new Integer[10000000];
        for (int i = 10000000-1; i >=0 ; i--) {
            arr[i]=i;
        }
        System.out.println(Arrays.toString(arr));
        LocalDateTime start = LocalDateTime.now();
        sort(arr);
        LocalDateTime end = LocalDateTime.now();
        System.out.println(Arrays.toString(arr));
        System.out.println("希尔排序的时间:"+ Duration.between(start,end).getNano());
    }


    /**
     * 正序
     *
     * @param arr
     * @param <T>
     */
    public static <T> void sort(Comparable<T>[] arr) {
        
       int h=1;
       while (h<arr.length/2) {
           h = 2 * h + 1;
       }
       while (h>=1){
           for (int  i= h; i <= arr.length-1; i+=h) {
               for (int j = i; j >=h; j-=h) {
                   if(greater(arr[j-h],arr[j])){
                       exch(arr,j,j-h);
                   }else {
                       break;
                   }
               }
           }
           h=h/2;
       }
       
    }

    /**
     * 比较大小，如果c1比c2大，返回true,否则false，正序
     *
     * @param c1
     * @param c2
     * @return
     */
    private static boolean greater(Comparable c1, Comparable c2) {
        return c1.compareTo(c2) > 0 ? Boolean.TRUE : Boolean.FALSE;
    }

    /**
     * 将arr数组中i角标和j角标位置互换
     *
     * @param arr 数组
     * @param i   角标
     * @param j   角标
     * @param <T>
     */
    private static <T> void exch(T[] arr, int i, int j) {
        T temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

插入排序最坏情况时候分析法

public class Insertion {
    public static void main(String[] args) {
        Integer arr[] = new Integer[10000000];
        for (int i = 10000000-1; i >=0 ; i--) {
            arr[i]=i;
        }
        System.out.println(Arrays.toString(arr));
        LocalDateTime start = LocalDateTime.now();
        sort(arr);

        LocalDateTime end = LocalDateTime.now();
        System.out.println(Arrays.toString(arr));
        System.out.println("插入排序的时间:"+ Duration.between(start,end).getNano());
    }
    /**
     * 正序
     *
     * @param arr
     * @param <T>
     */
    public static <T> void sort(Comparable<T>[] arr) {
        for (int i = 1; i <arr.length ; i++) {
            for (int j = i; j >0 ; j--) {
                if(greater(arr[j-1],j)){
                    exch(arr,j-1,j);
                }else {
                    break;
                }
            }

        }
    }
    /**
     * 比较大小，如果c1比c2大，返回true,否则false，正序
     *
     * @param c1
     * @param c2
     * @return
     */
    private static boolean greater(Comparable c1, Comparable c2) {
        return c1.compareTo(c2) > 0 ? Boolean.TRUE : Boolean.FALSE;
    }

    private static <T> boolean greater(Comparator comparator, T c1, T c2) {
        return comparator.compare(c1,c2 ) > 0 ? Boolean.TRUE : Boolean.FALSE;
    }

    /**
     * 将arr数组中i角标和j角标位置互换
     *
     * @param arr 数组
     * @param i   角标
     * @param j   角标
     * @param <T>
     */
    private static <T> void exch(T[] arr, int i, int j) {
        T temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

希尔排序的时间:178000000
插入排序的时间:273000000

这篇关于初识希尔排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航