图解Java中插入排序算法的原理与实现

目录
  • 一、基本思想
  • 二、算法分析
    • 1、算法描述
    • 2、过程分析
  • 三、算法实现

一、基本思想

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

二、算法分析

1、算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

  • 从第一个元素开始，该元素可以认为已经被排序；
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  • 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  • 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  • 将新元素插入到该位置后；
  • 重复步骤2~5。

2、过程分析

（1）、将第一个元素 (1) 标记为已经排序过。

（2）、提取第一个没有排序过的元素 (28)。

（3）、找出插入提取元素的地方；和已经排序过的元素 1 比较。

（4）、1 > 28 不成立（False）, 在现有位置上插入一个元素。

（5）、找出插入提取元素的地方；和已经排序过的元素 28 比较。

（6）、28 > 3 成立（True）, 则将现在已经排序过的元素({val1}) 向右移动1格。

（7）、找出插入提取元素的地方；和已经排序过的元素 1 比较。

（8）、1 > 3 不成立（False）, 在现有位置上插入一个元素。

（9）、以此类推

三、算法实现

package com.algorithm.tenSortingAlgorithm;

import java.util.Arrays;

public class InsertionSort {
    private static void insertionSort(int[] arr) {
        int preIndex, current;
        for (int i = 1; i < arr.length; i++) {
            preIndex = i - 1;
            current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

到此这篇关于图解Java中插入排序算法的原理与实现的文章就介绍到这了,更多相关Java插入排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

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

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

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

  • Java 十大排序算法之插入排序刨析

    Java 十大排序算法之插入排序刨析

    目录 插入排序原理 插入排序API设计 插入排序代码实现 插入排序的时间复杂度分析 插入排序原理 ①把所有元素分成已排序和未排序两组 ②找到未排序组的第一个元素,向已经排序的组中进行插入 ③倒序遍历已经排好的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他元素向后移动一位 插入排序API设计 类名 Insertion 构造方法 Insertion():创建Insertion对象 成员方法 1.public static void sort

  • 详解直接插入排序算法与相关的Java版代码实现

    详解直接插入排序算法与相关的Java版代码实现

    直接插入排序 直接插入排序的思路很容易理解,它是这样的: 1.把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的. 2.从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置. 3.重复上述过程直到最后一个元素被插入有序子数组中. 4.排序完成. 示例: 思路很简单,但代码并非像冒泡排序那么好写.首先,如何判断合适的位置?大于等于左边.小于等于右边?不行,很多边界条件需要考虑,而且判断次数太多.其次,数组中插入元素,必然需要移动大量元素,如何控制它们

  • Java经典排序算法之插入排序

    Java经典排序算法之插入排序

    一.算法原理 插入排序法:所谓插入排序法乃是将一个数目插入该占据的位置. 假设我们输入的是 "53,27,36,15,69,  42" 我们从第二个数字开始,这个数字是27,我们的任务只要看看27有没有正确的位置,我们的做法是和这个数字左边的数字来比,因此我们比较27和53,27比53小,所以我们就交换27和53,原来的排列就变成了"27, 53, 36, 15, 69, 42 " 接下来,我们看第3个数字有没有在正确的位置.这个数字是36,它的左边数字是53,36

  • java实现插入排序算法

    java实现插入排序算法

    1.算法概念. 每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序. 2.算法思想. 假设待排序的记录存放在数组R[1..n]中.初始时,R[1]自成1个有序区,无序区为R[2..n].从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区. public static void insertSort(int[] array) { int len = array.length; for (int i = 1; i < len;

  • 图解Java中插入排序算法的原理与实现

    图解Java中插入排序算法的原理与实现

    目录 一.基本思想 二.算法分析 1.算法描述 2.过程分析 三.算法实现 一.基本思想 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入. 二.算法分析 1.算法描述 一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下: 从第一个元素开始,该元素可以认为已经被排序: 取出下一个元素,在已经排序的元素序列中从后向前扫描: 如果该元素(已排序)大于新元素,将

  • 图解Java中归并排序算法的原理与实现

    图解Java中归并排序算法的原理与实现

    目录 一.基本思想 二.算法分析 1.算法描述 2.过程分析 3.动图演示 三.算法实现 一.基本思想 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并. 二.算法分析 1.算法描述 把长度为n的输入序列分成两个长度为n/2的子序列:对这两个子序列分别采用归并排序:将两个排序好的子序列合并

  • Java中Prime算法的原理与实现详解

    Java中Prime算法的原理与实现详解

    目录 Prim算法介绍 1.点睛 2.算法介绍 3. 算法步骤 4.图解 Prime 算法实现 1.构建后的图 2.代码 3.测试 Prim算法介绍 1.点睛 在生成树的过程中,把已经在生成树中的节点看作一个集合,把剩下的节点看作另外一个集合,从连接两个集合的边中选择一条权值最小的边即可. 2.算法介绍 首先任选一个节点,例如节点1,把它放在集合 U 中,U={1},那么剩下的节点为 V-U={2,3,4,5,6,7},集合 V 是图的所有节点集合. 现在只需要看看连接两个集合(U 和 V-U)

  • Java实现插入排序算法可视化的示例代码

    Java实现插入排序算法可视化的示例代码

    参考文章 图解Java中插入排序算法的原理与实现 实现效果 示例代码 import java.awt.*; public class AlgoVisualizer { private static int DELAY = 40; private InsertionSortData data; private AlgoFrame frame; public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){ // 初始化数据 data =

  • 详解Java中KMP算法的图解与实现

    详解Java中KMP算法的图解与实现

    目录 图解 代码实现 图解 kmp算法跟之前讲的bm算法思想有一定的相似性.之前提到过,bm算法中有个好后缀的概念,而在kmp中有个好前缀的概念,什么是好前缀,我们先来看下面这个例子. 观察上面这个例子,已经匹配的abcde称为好前缀,a与之后的bcde都不匹配,所以没有必要再比一次,直接滑动到e之后即可. 那如果好前缀中有互相匹配的字符呢? 观察上面这个例子,这个时候如果我们直接滑到好前缀之后,则会过度滑动,错失匹配子串.那我们如何根据好前缀来进行合理滑动? 其实就是看当前的好前缀的前缀和后缀

  • java 中基本算法之希尔排序的实例详解

    java 中基本算法之希尔排序的实例详解 希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本.希尔排序是非稳定排序算法.该方法因DL．Shell于1959年提出而得名. 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止. 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差

  • 详解Java中AC自动机的原理与实现

    详解Java中AC自动机的原理与实现

    目录 简介 工作过程 数据结构 初始化 构建字典树 构建失败指针 匹配 执行结果 简介 AC自动机是一个多模式匹配算法,在模式匹配领域被广泛应用,举一个经典的例子,违禁词查找并替换为***.AC自动机其实是Trie树和KMP 算法的结合,首先将多模式串建立一个Tire树,然后结合KMP算法前缀与后缀匹配可以减少不必要比较的思想达到高效找到字符串中出现的匹配串. 如果不知道什么是Tire树,可以先查看:详解Java中字典树(Trie树)的图解与实现 如果不知道KMP算法,可以先查看:详解Java中

  • Java中GC的工作原理详细介绍

    Java中GC的工作原理 引子:面试时被问到垃圾回收机制,只是粗略的讲'程序员不能直接对内存操作,jvm负责对已经超过作用域的对象回收处理',面官表情呆滞,也就没再继续深入. 转文: 一个优秀的Java程序员必须了解GC的工作原理.如何优化GC的性能.如何与GC进行有限的交互,有一些应用程序对性能要求较高,例如嵌入式系统.实时系统等,只有全面提升内存的管理效率,才能提高整个应用程序的性能.本文将从GC的工作原理.GC的几个关键问题进行探讨,最后提出一些Java程序设计建议,如何从GC角度提高Ja

  • 详解Java 中泛型的实现原理

    泛型是 Java 开发中常用的技术,了解泛型的几种形式和实现泛型的基本原理,有助于写出更优质的代码.本文总结了 Java 泛型的三种形式以及泛型实现原理. 泛型 泛型的本质是对类型进行参数化,在代码逻辑不关注具体的数据类型时使用.例如:实现一个通用的排序算法,此时关注的是算法本身,而非排序的对象的类型. 泛型方法 如下定义了一个泛型方法, 声明了一个类型变量,它可以应用于参数,返回值,和方法内的代码逻辑. class GenericMethod{ public <T> T[] sort(T[]

  • Java实现雪花算法的原理

    Java实现雪花算法的原理

    SnowFlake 算法,是 Twitter 开源的分布式 id 生成算法.其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 id.在分布式系统中的应用十分广泛,且ID 引入了时间戳,基本上保持自增的,后面的代码中有详细的注解. 这 64 个 bit 中,其中 1 个 bit 是不用的,然后用其中的 41 bit 作为毫秒数,用 10 bit 作为工作机器 id,12 bit 作为序列号. 给大家举个例子吧,比如下面那个 64 bit 的 long 型数字: 第一个部分

随机推荐