目录

希尔排序

排序原理

代码展示

希尔排序的时间复杂度分析

今天给大家分享的笔记是关于希尔排序

有点像 插入排序 的升级版~

希尔排序

      希尔排序是插入排序的一种，又称"缩小增量排序”，是插入排序算法的一种更高效的改进版本。 前面学习插入排序的时候，我们会发现一个很不友好的事儿，如果已排序的分组元素为{2.5,7,9,10}，未排序的分组元素为(1,8}，那么下一个待插入元素为1，我们需要拿着1从后往前，依次和10,9,7,5,2进行交换位置，才能完成真正的插入，每次交换只能和相邻的元素交换位置。

    

      那如果我们要提高效率，直观的想法就是一次交换，能把1放到更前面的位置，比如一次交换就能把1插到2和5之间，这样一次交换1就向前走了5个位置，可以减少交换的次数，这样的需求如何实现呢?接下来我们来看看希尔排序的原理。

     

需求∶

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

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

    

排序原理

1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组;

2.对分好组的每一组数据完成插入排序;

3.减小增长量，最小减为1，重复第二步操作。

       

     

      增长量h的确定:增长量h的值每一固定的规则，我们这里采用以下规则

        int h=1;
        while(h<数组的长度/2){
            h=2h+1;
        }
        //循环结束后我们就可以确定h的最大值
        h的减小规则为：
        h=h/2

     

     

代码展示

Shell方法

public class Shell {
    
    public static void sort(Comparable[] a){
        //1.根据数组a的长度，确定增长量h的初始值
        int h=1;
        while(h=1){
            //排序
            //2.1.找到待插入的元素
            for (int i = h; i < a.length; i++) {
                //2.2.把待插入的元素插入到有序数列中
                for (int j = i; j>=h; j-=h) {
                    //带插入元素是a[j],比较a[j]和a[j-h];
                    if(greater(a[j-h],a[j])){
                        //交换元素
                        exch(a,j-h,j);
                    }else{
                        //带插入元素已经找到了合适的位置，结束循环
                        break;
                    }
                }
            }
            //减小h的值
            h=h/2;
        }
    }

    
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }

    
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

测试类

import java.util.Arrays;

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

    

希尔排序的时间复杂度分析

      在希尔排序中，增长量h并没有固定的规则，有很多论文研究了各种不同的递增序列，但都无法证明某个序列是最好的，对于希尔排序的时间复杂度分析，已经超出了我的学习范围，所以在这里就不做分析了。我们可以使用事后分析法对希尔排序和插入排序做性能比较。

        

      我有一个123.txt文件，里面存放的是从100000到1的逆向数据，我们可以根据这个批量数据完成测试。测试的思想∶在执行排序前前记录一个时间，在排序完成后记录一个时间，两个时间的时间差就是排序的耗时。

        

      希尔排序和插入排序性能比较测试代码:

public class SortCompare {
    public static void main(String[] args) throws IOException {
        ArrayList list = new ArrayList<>();

        BufferedReader reader = new BufferedReader(new FileReader("E:\study\study\JAVA\java数据结构\Text\高级排序\src\希尔排序\Text\123.txt"));
        String line = null;
        while((line=reader.readLine())!=null){
            //line是字符串，把line转换成Integer储存到集合
            int i = Integer.parseInt(line);
            list.add(i);
        }
        reader.close();
        //集合转数组
        Integer[] a = new Integer[list.size()];
        list.toArray(a);
        //测试性能
//        DeShell(a);
//        DeInsertion(a);

    }

    public static void DeShell(Integer[] a){
        long start = System.currentTimeMillis();
        Shell.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("希尔排序执行的时间为："+(end-start)+"毫秒");
    }

    public static void DeInsertion(Integer[] a){
        long start = System.currentTimeMillis();
        Insertion.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("插入排序执行的时间为："+(end-start)+"毫秒");
    }
}
//插入排序执行的时间为：13416毫秒
//希尔排序执行的时间为：15毫秒
//由此可见希尔排序完虐插入排序

            

      这里的 Shell 和 Insertion 是已经写好的方法API，具体代码请查看 插入排序 ，希尔排序两文。

       

那么今天的分享结束啦！

下一篇 归并排序 更精彩！

喜欢记得一键三连哦~