纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

Java 排序算法 Java 十大排序算法之希尔排序刨析

龍弟-idea   2021-11-18 我要评论
想了解Java 十大排序算法之希尔排序刨析的相关内容吗,龍弟-idea在本文为您仔细讲解Java 排序算法的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java,排序算法,Java,希尔排序,下面大家一起来学习吧。

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

希尔排序原理

1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组。
2.对分好组的每一组数据完成插入排序。
3.减小增长量,最小减为1,重复第二步操作。

希尔排序的API设计

类名 Shell
构造方法 Shell():创建Shell对象
成员方法

1.public static void sort(Comparable[] a):对数组内的元素进行排序

2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w

3.private static void exchange(Comparable[] a,int i,int j):交换a数组中,索引i和索引j处的值

希尔排序的代码实现

public class Shell {
    //对数组a中的元素进行排序
    public static void sort(Comparable[] a){
        int N=a.length;
        //确定增长量h的最大值
        int h=1;
        while(h<N/2){
            h=2*h+1;
        }
        //当增长量h小于1,排序结束
        while(h>=1){
            //找到待插入的元素
            for(int i=h;i<N;i++){
                //a[i]就是待插入的元素
                //把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中
                for(int j=i;j>=h;j-=h){
                    //a[j]就是待插入的元素,依次和a[j-h],a[j-2h],a[j-3h]进行比较,如果a[j]小,
                    // 那么交换位置,如果不小于,a[j]大,则插入完成
                    if(greater(a[j-h],a[j])){
                        exchange(a,j,j-h);
                    }else{
                        break;
                    }
                }
            }
            h/=2;
        }
    }
    //比较v元素是否大于w元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    //数组元素i和j交换位置
    private static void exchange(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
class Test{
    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));
    }
}

测试结果:

由于增量h没有固定的值,希尔排序的时间复杂度较为复杂,但在处理大批量数据时,希尔排序的性能高于插入排序!


相关文章

猜您喜欢

  • CentOS 8.4安装Docker CentOS 8.4安装Docker的详细教程

    想了解CentOS 8.4安装Docker的详细教程的相关内容吗,追逐时光者在本文为您仔细讲解CentOS 8.4安装Docker的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:CentOS,8.4安装Docker,下面大家一起来学习吧。..
  • Docker制作镜像 Docker制作镜像的完整过程

    想了解Docker制作镜像的完整过程的相关内容吗,水妖3在本文为您仔细讲解Docker制作镜像的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Docker制作镜像,Docker,镜像制作,下面大家一起来学习吧。..

网友评论

Copyright 2020 www.moon-script.com 【月光下载】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式