Java实现直接插入排序与折半插入排序的示例详解

目录
  • 1.直接插入排序
  • 2. 折半插入排序

1.直接插入排序

插入排序的基本思想: 主要分为两个区间, 无序区间和有序区间, 每次选择无序区间的第一个元素, 在有序区间内选择合适的位置进行插入操作.

插入过程如下图所示:

代码:

public class InsertSort {
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j+1] = array[j];
                } else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

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

运行结果:

性能分析:

2. 折半插入排序

折半插入的详细过程如下:

代码:

public class InsertSort {
    public static void bsInsertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int left = 0;
            int right = i;
            while (left < right) {
                int aver = (left + right) / 2;
                if (tmp >= array[aver]) {
                    left = aver + 1;
                } else {
                    right = aver;
                }
            }
            for (int j = i; j > left; j--) {
                array[j] = array[j-1];
            }
            array[left] = tmp;
        }
    }

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

运行结果:

性能分析:

以上就是Java实现直接插入排序与折半插入排序的示例详解的详细内容，更多关于Java插入排序的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Java排序算法总结之插入排序

    本文实例讲述了Java插入排序方法.分享给大家供大家参考.具体分析如下: 有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到插入排序法.本文主要介绍的是插入排序的java实现.   插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据.比较和交换的时间复杂度为O(n^2),算法自适应,对于数据已基本有序的情况,时间复杂度为O(n),算法稳定,开销很低.算法适合于数据已基本有序或者数据量

  • Java实现直接插入排序和折半插入排序算法示例

    Java实现直接插入排序和折半插入排序算法示例

    直接插入排序​ 1 排序思想: 将待排序的记录Ri插入到已经排好序的记录R1,R2,--,R(N-1)中. 对于一个随机序列而言,就是从第二个元素开始,依次将这个元素插入到它之前的元素中的相应位置.它之前的元素已经排好序. 第1次排序:将第2个元素插入到前边的有序列表(此时前边只有一个元素,当然是有序的),之后,这个序列的前2个元素就是有序的了. 第2次排序:将第3个元素插入到前边长度为2的有序列表,使得前2个元素是有序的. 以此类推,直到将第N个元素插入到前面长度为(N-1)的有序列表中. 2

  • java直接插入排序示例

    java直接插入排序示例

    影响排序效率的一般从3个方面比较:数据比较的次数,数据移动的次数,内存空间占用的大小.我们就冒泡排序.选择排序.插入排序.快速排序做一个总的比较.一般情况下不会使用冒泡排序算法,因为它的比较次数和移动次数在几种排序算法中都是最多的,它的唯一好处是算法简单,易于理解,所以在数据量很小的时候它会有些应用价值.选择排序在比较次数上和冒泡排序一样,都是n的平方,但它把交换的次数降低到了最低,所以在数据量很小且交换数据相对于比较数据更加耗时的情况下,可以应用选择排序.在大多数情况下,当数据量比较小或基本上

  • Java编程实现直接插入排序代码示例

    算法描述:对于给定的一个数组,初始时假设第一个记录自成一个有序序列,其余记录为无序序列.接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直至最后一个记录插入到有序序列中为止. 直接插入排序Java实现教程 示例1 public class Insert { public static void main(String[] args) { int a[] = {9,3,28,6,34,7,10,27,1,5,8}; show(a); for (int i=1;i

  • JAVA十大排序算法之插入排序详解

    JAVA十大排序算法之插入排序详解

    目录 插入排序 代码实现 动图演示 代码实现 时间复杂度 算法稳定性 总结 插入排序 当我们在玩扑克牌的时候,总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列. 插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的. 1.对于未排序数据(一般取数组的二个元素,把第一个元素当做有序数组),在已排序序列中从左往右扫描,找到相应位置并插入. 2.为了给要插入的元素腾出空

  • Java实现插入排序

    Java实现插入排序

    问题描述 利用插入排序把一列数组按从小到大或从大到小排序 (一).插入排序思想 以从小到大为例: 1.第一轮插入,从第二个数开始,与前面的数依次比较,遇到比自己小的数,就插入到该数后面的位置 2.第二轮插入,从第三个数开始,与前面的数依次比较,遇到比自己小的数,就插入到该数后面的位置 3.如此循环,直到所有数从小到大排列 (二).问题分析 1. 输入数组 根据用户输入的进行排序的数字数量n,建立一个长度为n的数组 public static void main (String[] args){

  • Java 直接插入排序的三种实现

    直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止. 设数组为a[0-n-1]. 1. 初始时,a[0]自成1个有序区,无序区为a[1..n-1].令i=1 2. 将a[i]并入当前的有序区a[0-i-1]中形成a[0-i]的有序区间. 3. i++并重复第二步直到i==n-1.排序完成. 下面给出严格按照定义书写的代码(由小到大排序): void Insertsort1(int a[

  • java中Servlet监听器的工作原理及示例详解

    监听器就是一个实现特定接口的普通java程序,这个程序专门用于监听另一个java对象的方法调用或属性改变,当被监听对象发生上述事件后,监听器某个方法将立即被执行. 监听器原理 监听原理 1.存在事件源 2.提供监听器 3.为事件源注册监听器 4.操作事件源,产生事件对象,将事件对象传递给监听器,并且执行监听器相应监听方法 监听器典型案例:监听window窗口的事件监听器 例如:swing开发首先制造Frame**窗体**,窗体本身也是一个显示空间,对窗体提供监听器,监听窗体方法调用或者属性改变:

  • java中常见的6种线程池示例详解

    之前我们介绍了线程池的四种拒绝策略,了解了线程池参数的含义,那么今天我们来聊聊Java 中常见的几种线程池,以及在jdk7 加入的 ForkJoin 新型线程池 首先我们列出Java 中的六种线程池如下 线程池名称 描述 FixedThreadPool 核心线程数与最大线程数相同 SingleThreadExecutor 一个线程的线程池 CachedThreadPool 核心线程为0,最大线程数为Integer. MAX_VALUE ScheduledThreadPool 指定核心线程数的定时

  • java面向对象设计原则之里氏替换原则示例详解

    目录 概念 实现 拓展 概念 里氏替换原则是任何基类出现的地方,子类一定可以替换它:是建立在基于抽象.多态.继承的基础复用的基石,该原则能够保证系统具有良好的拓展性,同时实现基于多态的抽象机制,能够减少代码冗余. 实现 里氏替换原则要求我们在编码时使用基类或接口去定义对象变量,使用时可以由具体实现对象进行赋值,实现变化的多样性,完成代码对修改的封闭,扩展的开放.如:商城商品结算中,定义结算接口Istrategy,该接口有三个具体实现类,分别为PromotionalStrategy (满减活动,两

  • java面向对象设计原则之接口隔离原则示例详解

    java面向对象设计原则之接口隔离原则示例详解

    目录 概念 实现 拓展 概念 小接口原则,即每个接口中不存在子类用不到却必须实现的方法,如果不然,就要将接口拆分.如下图所示定义了一个接口,包含了5个方法,实现类A用到了3个方法.实现类B用到了3个方法,类图如下: 类A没有方法4.方法5,却要实现它:类B没有方法2.方法3,但还是要实现这两个方法,不符合接口隔离原则.改造为将其拆分为三个接口,实现方式改为下图所示,符合接口隔离原则: 实现 面向对象机制中一个类可以实现多个接口,通过多重继承分离,通过接口多继承(实现)来实现客户的需求,代码更加清

  • java面向对象设计原则之合成复用原则示例详解

    java面向对象设计原则之合成复用原则示例详解

    目录 概念 示例 拓展 概念 尽量使用合成/聚合,而不是使用继承实现复用.所谓的合成/聚合是指一个对象里持有另外一个类的对象,通过调用这些对象的方法得到复用已有功能的目的.如:报文解译程序中,按照继承复用可以设计为: 子类调用父类的方法即可完成水文报文解译.气象解译中通用方法:子类中一定包含了父类的方法,这个叫继承复用. 按照合成/聚合原则设计为: 水文协议和气象协议中,持有编码和位制转换对象,通过调用对象方法即可完成复用. 示例 数据库连接的复用:首先看通过集成关系复用数据连接代码如下 pub

  • java设计模式七大原则之开闭原则示例详解

    java设计模式七大原则之开闭原则示例详解

    目录 1.什么是开闭原则? 2.违反Ocp代码案例 3.遵守Ocp代码案例 1.什么是开闭原则? 开闭原则(Open Closed Principle)是编程中最基础.最重要的设计原则.一个软件实体如类,模块和函数应该对扩展开放(对提供方),对修改关闭(对使用方).用抽象构建框架,用实现扩展细节.当软件需要变化时,尽量通过扩展软件实体的行为来实现变化,而不是通过修改已有的代码来实现变化.编程中遵循其它原则,以及使用设计模式的目的就是遵循开闭原则. 2.违反Ocp代码案例 package com.

  • java编程创建型设计模式工厂方法模式示例详解

    java编程创建型设计模式工厂方法模式示例详解

    目录 1.什么是工厂方法模式? 2.案例实现 3.JDK中的工厂方法模式 1.什么是工厂方法模式? 工厂方法模式设计方案:  将披萨项目的实例化功能抽象成抽象方法,在不同的口味点餐子类中具体实现. 工厂方法模式:  定义了一个创建对象的抽象方法,由子类决定要实例化的类.工厂方法模式将对象的实例化推迟到子类. 何时使用?  不同条件下创建不用实例时.方法是让子类实现工厂接口. 2.案例实现 假如说,我们现在有这样一个需求:客户在点披萨时,可以点不同口味的披萨,比如北京的奶酪pizza.北京的胡椒p

  • Java实现超简单抖音去水印的示例详解

    Java实现超简单抖音去水印的示例详解

    目录 一.前言 二.原理与步骤 三.代码实现 四.总结 一.前言 抖音去水印方法很简单,以前一直没有去研究,以为搞个去水印还要用到算法去除,直到动手的时候才发现这么简单,不用编程基础都能做. 二.原理与步骤 其实抖音它是有一个隐藏无水印地址的,只要我们找到那个地址就可以了 1.我们在抖音找一个想要去水印的视频链接 注意:这里一定要是https开头的,不是口令 打开浏览器访问: 访问之后会重定向到这个地址,后面有一串数字,这个就是视频的id,他是根据这个唯一id来找到视频播放的 按F12查看网络请

  • java zxing合成复杂二维码图片示例详解

    java zxing合成复杂二维码图片示例详解

    目录 说明: 整体思路: 图片合成四部曲 踩过的坑 说明: 最近接到需要将二维码合成复杂图片的需求,要求给二维码上下或者左侧添加相关文字描述,技术没有难点,整理本文主要记录思路和踩过的坑. 整体思路: 引入zxing成熟的二维码生成接口,生成标准二维码文件,通过java图形图像处理API为二维码添加相关文字描述,根据需要,可以为合成后的图片添加相关背景.示例如下图所示: 1.先拿点位图来说,生成二维码图片核心代码如下 /** * 定义二维码的参数 */ HashMap<EncodeHintTyp

  • java EasyExcel面向Excel文档读写逻辑示例详解

    java EasyExcel面向Excel文档读写逻辑示例详解

    目录 正文 1 快速上手 1.1 引入依赖 1.2 导入与导出 2 实现原理 2.1 @RequestExcel 与 @ResponseExcel 解析器 2.2 RequestMappingHandlerAdapter 后置处理器 3 总结 正文 EasyExcel是一款由阿里开源的 Excel 处理工具.相较于原生的Apache POI,它可以更优雅.快速地完成 Excel 的读写功能,同时更加地节约内存. 即使 EasyExcel 已经很优雅了,但面向 Excel 文档的读写逻辑几乎千篇一

随机推荐