广告
返回顶部
首页 > 资讯 > 后端开发 > Python >JAVA十大排序算法之插入排序详解
  • 176
分享到

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

2024-04-02 19:04:59 176人浏览 泡泡鱼

Python 官方文档:入门教程 => 点击学习

摘要

目录插入排序代码实现动图演示代码实现时间复杂度算法稳定性总结插入排序 当我们在玩扑克牌的时候,总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列。 插入排序是指在待排序的元素中,假设

插入排序

当我们在玩扑克牌的时候,总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列。

插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。

1.对于未排序数据(一般取数组的二个元素,把第一个元素当做有序数组),在已排序序列中从左往右扫描,找到相应位置并插入。

2.为了给要插入的元素腾出空间,需要将插入位置之后的已排序元素在都向后移动一位。

image-20210728162127494

代码实现

对下面数组实现排序:{15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}

动图演示

插入排序

代码实现


public class InsertionSort {
    public static final int[] ARRAY = {15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1};
    public static int[] sort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        //待排序数据,改数据之前的已被排序
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            //已被排序数据的索引
            int index = i;
            current = array[index + 1];
            //将当前元素后移一位
            while (index >= 0 && current < array[index]) {
                array[index + 1] = array[index];
                index--;
            }
            //插入
            array[index + 1] = current;
        }
        return array;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

时间复杂度

在上面图示中,第一趟循环比较一次,第二趟循环两次,依次类推,则最后一趟比较n-1次:

1 + 2 + 3 +… + n-1 = n*(n-1)/2

也就是说,在最坏的情况下(逆序),比较的时间复杂度为O(n2)

在最优的情况下,即while循坏总是假的,只需当前数跟前一个数比较一下就可以了,这时一共需要比较n-1次,时间复杂度为O(n)。

算法稳定性

在比较的时候,过两个数相等的话,不会进行移动,前后两个数的次序不会发生改变,所以插入排序是稳定的。

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注编程网的更多内容!

--结束END--

本文标题: JAVA十大排序算法之插入排序详解

本文链接: https://www.lsjlt.com/news/133280.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • JAVA十大排序算法之插入排序详解
    目录插入排序代码实现动图演示代码实现时间复杂度算法稳定性总结插入排序 当我们在玩扑克牌的时候,总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列。 插入排序是指在待排序的元素中,假设...
    99+
    2022-11-12
  • Java 十大排序算法之插入排序刨析
    目录插入排序原理插入排序API设计插入排序代码实现插入排序的时间复杂度分析插入排序原理 ①把所有元素分成已排序和未排序两组 ②找到未排序组的第一个元素,向已经排序的组中进行插入 ③倒...
    99+
    2022-11-12
  • JAVA十大排序算法之堆排序详解
    目录堆排序知识补充二叉树满二叉树完全二叉树二叉堆代码实现时间复杂度算法稳定性思考总结堆排序 这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆。它具有以下特点: ...
    99+
    2022-11-12
  • JAVA十大排序算法之桶排序详解
    目录桶排序代码实现时间复杂度算法稳定性总结桶排序 桶排序是计数排序的升级,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过函数的某种映射关系,将待排序数组...
    99+
    2022-11-12
  • JAVA十大排序算法之基数排序详解
    目录基数排序代码实现时间复杂度算法稳定性基数排序 vs 桶排序 vs 计数排序总结基数排序 常见的数据元素一般是由若干位组成的,比如字符串由若干字符组成,整数由若干位0~9数字组成。...
    99+
    2022-11-12
  • JAVA十大排序算法之冒泡排序详解
    目录冒泡排序代码实现代码实现时间复杂度算法稳定性总结冒泡排序 1.从数组头开始,比较相邻的元素。如果第一个比第二个大(小),就交换它们两个 2.对每一对相邻元素作同样的工作,从开始第...
    99+
    2022-11-12
  • JAVA十大排序算法之选择排序详解
    目录选择排序代码实现动图演示代码实现时间复杂度算法稳定性总结选择排序 1.找到数组中最大(或最小)的元素 2.将它和数组的第一个元素交换位置(如果第一个元素就是最大(小)元素那么它就...
    99+
    2022-11-12
  • JAVA十大排序算法之希尔排序详解
    目录希尔排序代码实现时间复杂度算法稳定性总结希尔排序 一种基于插入排序的快速的排序算法。简单插入排序对于大规模乱序数组很慢,因为元素只能一点一点地从数组的一端移动到另一端。例如,如果...
    99+
    2022-11-12
  • JAVA十大排序算法之归并排序详解
    目录归并排序怎么分怎么治代码实现时间复杂度算法稳定性总结归并排序 归并,指合并,合在一起。归并排序(Merge Sort)是建立在归并操作上的一种排序算法。其主要思想是分而治之。什么...
    99+
    2022-11-12
  • JAVA十大排序算法之快速排序详解
    目录快速排序问题思路荷兰国旗问题代码实现时间复杂度算法稳定性总结快速排序 快速排序是对冒泡排序的一种改进,也是采用分治法的一个典型的应用。JDK中Arrays的sort()方法,具体...
    99+
    2022-11-12
  • JAVA十大排序算法之计数排序详解
    目录计数排序问题代码实现时间复杂度算法稳定性总结计数排序 一种非比较排序。计数排序对一定范围内的整数排序时候的速度非常快,一般快于其他排序算法。但计数排序局限性比较大,只限于对整数进...
    99+
    2022-11-12
  • TypeScript十大排序算法插入排序实现示例详解
    目录一. 插入排序的定义二. 插入排序的流程三. 插入排序的图解四. 插入排序的代码五. 插入排序的时间复杂度六. 插入排序的总结一. 插入排序的定义 插入排序就像是你打扑克牌,你...
    99+
    2023-02-23
    TypeScript插入排序算法 TypeScript 算法
  • 排序算法图解之Java插入排序
    目录1.插入排序简介2.插入排序思想及图解3.插入排序代码实现1.插入排序简介 插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序...
    99+
    2022-11-13
    Java 插入排序算法 Java插入排序 Java 排序算法
  • Java十大排序算法之堆排序刨析
    二叉堆是完全二叉树或者是近似完全二叉树。 二叉堆满足二个特性︰ 1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。 2.每个结点的左子树和右子树都是一个二叉堆(都是最...
    99+
    2022-11-12
  • TypeScript十大排序算法插入排序怎么实现
    今天小编给大家分享一下TypeScript十大排序算法插入排序怎么实现的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。一. 插...
    99+
    2023-07-05
  • 排序算法之插入排序法解析
    目录什么是插入排序法算法优化心得体会什么是插入排序法 插入排序法是一种简单但有效的排序算法,其基本思想是将一个待排序的元素逐个插入到已经排好序的元素序列中,直至所有元素都被插入完成,...
    99+
    2023-08-08
    排序算法 插入排序法
  • Java 十大排序算法之希尔排序刨析
    目录希尔排序原理希尔排序的API设计希尔排序的代码实现希尔排序是插入排序的一种,又称"缩小增量排序”,是插入排序算法的一种更高效的改进版本。 希尔排序原理 1.选定一个增长量h,按照...
    99+
    2022-11-12
  • Java 十大排序算法之归并排序刨析
    目录归并排序原理归并排序API设计归并排序代码实现归并排序的时间复杂度分析归并排序原理 1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元...
    99+
    2022-11-12
  • Java 十大排序算法之选择排序刨析
    目录选择排序原理选择排序API设计选择排序代码实现选择排序的时间复杂度选择排序原理 ①假设第一个索引处的元素为最小值,和其他值进行比较,如果当前的索引处的元素大于其他某个索引处的值,...
    99+
    2022-11-12
  • Java 十大排序算法之冒泡排序刨析
    目录冒泡排序原理冒泡排序API设计冒泡排序的代码实现冒泡排序的时间复杂度分析冒泡排序原理 ①比较相邻的元素,如果前一个元素比后一个元素大,则交换这两个元素的位置 ②对每一对相邻的元素...
    99+
    2022-11-12
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作