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

直接插入排序

直接插入排序的思路很容易理解,它是这样的:
1.把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的。
2.从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
3.重复上述过程直到最后一个元素被插入有序子数组中。
4.排序完成。

示例:
思路很简单,但代码并非像冒泡排序那么好写。首先,如何判断合适的位置?大于等于左边、小于等于右边?不行,很多边界条件需要考虑,而且判断次数太多。其次,数组中插入元素,必然需要移动大量元素,如何控制它们的移动?
实际上,这并不是算法本身的问题,而多少和编程语言有点关系了。有时候算法本身已经很成熟了,到了具体的编程语言还是要稍作改动。这里讲的是Java算法,那就拿Java说事儿。
为了解决上述问题,我们对第二步稍作细化,我们不从子数组的起始位置开始比较,而从子数组尾部开始逆序比较,只要比需要插入的数大,就向后移动。直到不大于该数的数,那么,这个空出来的位置就安放需要插入的数字。因此,我们可以写出以下代码:
InsertArray.java

public class InsertArray {
  // 数组
  private long[] arr;

  // 数组中有效数据的大小
  private int elems;

  // 默认构造函数
  public InsertArray() {
    arr = new long[50];
  }

  public InsertArray(int max) {
    arr = new long[max];
  }

  // 插入数据
  public void insert(long value) {
    arr[elems] = value;
    elems++;
  }

  // 显示数据
  public void display() {
    for (int i = 0; i < elems; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  // 插入排序
  public void insertSort() {
    long select = 0L;
    for(int i = 1; i < elems; i++) {
      select = arr[i];
      int j = 0;
      for(j = i;j > 0 && arr[j - 1] >= select; j--) {
        arr[j] = arr[j - 1];
      }
      arr[j] = select;
    }
  }
}

测试类:
TestInsertArray.java

public class TestInsertArray {
  public static void main(String[] args) {
    InsertArray iArr = new InsertArray();
    iArr.insert(85);
    iArr.insert(7856);
    iArr.insert(12);
    iArr.insert(8);
    iArr.insert(5);
    iArr.insert(56);

    iArr.display();
    iArr.insertSort();
    iArr.display();
  }

}

打印结果:

算法性能/复杂度
现在讨论下直接插入算法的时间复杂度。无论输入如何,算法总会进行n-1轮排序。但是,由于每个元素的插入点是不确定的,受输入数据影响很大,其复杂度并不是一定的。我们可以分最佳、最坏、平均三种情况讨论。
1.最佳情况:由算法特点可知,当待排数组本身即为正序(数组有序且顺序与需要的顺序相同,于我们的讨论前提,即为升序)时为最佳,理由是这种情况下,每个元素只需要比较一次且无需移动。算法的时间复杂度为O(n);
2.最坏情况:很显然,当待排数组为逆序时为最坏情况,这种情况下我们的每轮比较次数为i-1, 赋值次数为i。总的次数为级数2n-1的前n项和,即n^2.算法的时间复杂度为O(n^2);
3.平均情况:由上述分析可以得到平均情况下算法的运算次数大约为(n^2)/2(注:这里计算以赋值和比较计,若按移动和比较,则大约为n^2/4),显然,时间复杂度还是O(n^2)。
至于算法的空间复杂度,所有移动均在数据内部进行,唯一的开销是我们引入了一个临时变量(有的数据结构书上称为“哨兵”),因此,其空间复杂度(额外空间)为O(1)。

算法稳定性
由于只需要找到不大于当前数的位置而并不需要交换,因此,直接插入排序是稳定的排序方法。

算法变种
如果待排列的数据比较多,那么每次从后往前找就造成了很大的开销,为了提高查找速度,可以采用二分查找(Binary Search)进行性能优化。由于二分查找的效率很高,保证了O(㏒n)复杂度,在数据比较多或输入数据趋向最坏情况时可以大幅提高查找效率。在有些书上将这种方法称为折半插入排序。它的代码实现比较复杂,以后有时间可以贴出来。
此外,还有2-路插入排序和表插入排序。2-路插入排序是在折半插入排序的基础上进一步改进,其移动次数大为降低,大约为n^2/8。但是,它并不能避免移动次数,也不能降低复杂度级别。表插入排序则完全改变存储结构,不移动记录,但需要维护一个链表,以链表的指针修改代替移动记录。因此,其复杂度仍然是O(n^2)。
有关2-路插入排序和表插入排序,可以参考严蔚敏、吴伟民编著的《数据结构》一书。

算法适用场景
插入排序由于O(n^2)的复杂度,在数组较大的时候不适用。但是,在数据比较少的时候,是一个不错的选择,一般做为快速排序的扩充。例如,在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快速排序的补充,用于少量元素的排序。又如,在JDK 7 java.util.Arrays所用的sort方法的实现中,当待排数组长度小于47时,会使用插入排序。

(0)

相关推荐

  • Java直接插入排序算法实现

    序:一个爱上Java最初的想法一直没有磨灭:"分享我的学习成果,不管后期技术有多深,打好基础很重要". 工具类Swapper,后期算法会使用这个工具类: 复制代码 代码如下: package com.meritit.sortord.util; /** * One util to swap tow element of Array *  * @author ysjian * @version 1.0 * @email ysjian_pingcx@126.com * @QQ 6466337

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

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

  • java直接插入排序示例

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

  • 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版代码实现

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

  • 详解如何热更新线上的Java服务器代码

    一.前言 1.热更新代码的场景 (1)当线上服务器出现问题时,有些时候现有的手段不足以发现问题所在,可能需要追加打印日志或者增加一些调试代码,如果我们去改代码重新部署,会破坏问题现场,可以通过热部署的手段来增加调试代码 (2)线上出现紧急bug,通过Review代码找到问题,修改好后打包部署的流程可能比较久,可以通过热部署代码及时解决问题 二.Arthas的使用 使用阿里巴巴开源的Java诊断工具---Arthas,他可以附着在我们的Java服务器进程上面,查看服务器状态,jvm状态等各种参数指

  • C语言详解数据结构与算法中枚举和模拟及排序

    目录 枚举 连号区间数 递增三元组 二分 双指针 前缀和 模拟 特别数的和 错误票据 排序 快速排序 归并排序 枚举 连号区间数 来源:第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组 小明这些天一直在思考这样一个奇怪而有趣的问题: 在 1∼N 的某个排列中有多少个连号区间呢? 这里所说的连号区间的定义是: 如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间. 当 N 很小的时候,小明可以

  • 详解C++图搜索算法之双端队列广搜

    目录 广度优先遍历 双端队列BFS 例题:AcWing 175. 电路维修 解题思路 AC代码 广度优先遍历 广度优先遍历是一种按照层次顺序进行访问的方法,它具有以下两种重要性质: 在访问完所有第i层的结点后,才会去访问第i+1层的结点 任意时刻,队列中至多有两个层次的结点.若其中一部分结点属于第i层,则另一部分结点属于第i+1层,并且所有第i层结点排在第i+1层之前.也就是说,广度优先遍历队列中的元素关于层次满足 双端队列BFS 在最基本的广度优先搜索中,每次沿着分支的扩展都记为“一步”,我们

  • 图文详解牛顿迭代算法原理及Python实现

    目录 1.引例 2.牛顿迭代算法求根 3.牛顿迭代优化 4 代码实战:Logistic回归 1.引例 给定如图所示的某个函数,如何计算函数零点x0 在数学上我们如何处理这个问题? 最简单的办法是解方程f(x)=0,在代数学上还有著名的零点判定定理 如果函数y=f(x)在区间[a,b]上的图象是连续不断的一条曲线,并且有f(a)⋅f(b)<0,那么函数y=f(x)在区间(a,b)内有零点,即至少存在一个c∈(a,b),使得f(c)=0,这个c也就是方程f(x)=0的根. 然而,数学上的方法并不一定

  • 详解python的字典及相关操作

    目录 什么是字典 创建一个字典 在原有字典上添加“键-值”对 修改字典中的值 删除键-值对 由类似对象组成的字典 遍历字典 什么是字典 字典是Python中最强大的数据类型之一,也是Python语言中唯一的映射类型.映射类型对象里哈希值(键,key)和指向的对象(值,value)是一对多的的关系,通常被认为是可变的哈希表,字典对象是可变的,它是一个容器类型,能存储任意个数的Python对象,其中也可包括其他容器类型. 字典类型与序列类型的区别:1.存取和访问数据的方式不同.2.序列类型只用数字类

  • Java 中的HashMap详解和使用示例_动力节点Java学院整理

    第1部分 HashMap介绍 HashMap简介 HashMap 是一个散列表,它存储的内容是键值对(key-value)映射. HashMap 继承于AbstractMap,实现了Map.Cloneable.java.io.Serializable接口. HashMap 的实现不是同步的,这意味着它不是线程安全的.它的key.value都可以为null.此外,HashMap中的映射不是有序的. HashMap 的实例有两个参数影响其性能:"初始容量" 和 "加载因子&quo

  • ArrayList详解和使用示例_动力节点Java学院整理

    第1部分 ArrayList介绍 ArrayList简介 ArrayList 是一个数组队列,相当于 动态数组.与Java中的数组相比,它的容量能动态增长.它继承于AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口. ArrayList 继承了AbstractList,实现了List.它是一个数组队列,提供了相关的添加.删除.修改.遍历等功能. ArrayList 实现了RandmoAccess接口,即提

  • Visual Studio Code (vscode) 配置C、C++环境/编写运行C、C++的教程详解(Windows)【真正的小白版】

    写在前面的前面:这篇文章vscode和cpp插件版本有点老了,仅供大家参考,最新的和最详细的更新见我的另一篇文章: https://www.jb51.net/article/183154.htm 写在前面: 由于这学期(或者说这一年)一直在忙别的,也没什么闲心看博客了,近期发现自己的这篇文章:整理:Visual Studio Code (vscode) 配置C.C++环境/编写运行C.C++(Windows)竟然有了好多访问,也有不少童鞋问各种问题,非常感谢大家的支持,本来是自己整理的没想到有这

  • Java 添加、删除、替换、格式化Word中的文本的步骤详解(基于Spire.Cloud.SDK for Java)

    Spire.Cloud.SDK for Java提供了TextRangesApi接口可通过addTextRange()添加文本.deleteTextRange()删除文本.updateTextRangeText()替换文本.updateTextRangeFormat()格式化文本等.本文将从以上方法介绍如何来实现对文本的操作.可参考以下步骤进行准备: 一.导入jar文件 创建Maven项目程序,通过maven仓库下载导入.以IDEA为例,新建Maven项目,在pom.xml文件中配置maven仓

随机推荐