文档章节

java插入排序

Demens
 Demens
发布于 2017/05/19 11:35
字数 380
阅读 4
收藏 0

精选30+云产品,助力企业轻松上云!>>>

一、基本概念

      插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。

二、java代码实现

public class InsertSort {
    public static void inserSort(int[] array){
        if (array==null||array.length<2){
            return;
        }

        for (int i=1;i<array.length;i++){  //默认第一个元素为有序队列,从第二个元素开始循环插入
           int position=array[i];          //设置第二个元素为要插入的数据
           int j=i-1;
            while (j>=0&&position<array[j]){
                array[j+1]=array[j];      //如果插入发数小于第j个元素,将第j个数向后移
                j--;
            }
            array[j+1]=position;         //插入
        }
    }

    public static void main(String ags[]){
        int[] array={2,6,4,7,3,-1};
        inserSort(array);
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
    }
}

三、性能分析

  • 稳定 
  • 空间复杂度O(1) 
  • 时间复杂度O(n2) 
  • 最差情况:反序,需要移动n*(n-1)/2个元素 
  • 最好情况:正序,不需要移动元素
上一篇: Java泛型详解
下一篇: 简单选择排序
Demens
粉丝 0
博文 11
码字总数 14760
作品 0
私信 提问
加载中
请先登录后再评论。
Java基础语法(8)-数组中的常见排序算法

title: Java基础语法(8)-数组中的常见排序算法 blog: CSDN data: Java学习路线及视频 1.基本概念 排序: 是计算机程序设计中的一项重要操作,其功能是指一个数据元素集合或序列重新排列成一个按...

BenCoper
04/01
0
0
Java 排序

Java二分查找法 Java冒泡排序 Java选择排序 Java插入排序 Java希尔排序 Java计数排序 Java快排算法 Java归并排序 Java堆排序 动图演示

GordonDicaprio
04/07
0
0
常见排序算法及对应的时间复杂度和空间复杂度

本人免费整理了Java高级资料,涵盖了Java、Redis、MongoDB、MySQL、Zookeeper、Spring Cloud、Dubbo高并发分布式等教程,一共30G,需要自己领取。 传送门:https://mp.weixin.qq.com/s/Jzdd...

osc_1i3i83o4
2019/09/20
2
0
Java基础语法(8)-数组中的常见排序算法

title: <font color=red>Java基础语法(8)-数组中的常见排序算法 </font> blog: CSDN data: Java学习路线及视频 1.基本概念 <font color =FF9933 >排序</font>: 是计算机程序设计中的一项重要......

osc_z7xhzbll
04/01
4
0
java 通配符的应用— java 排序算法

这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对j...

天地一MADAO_
2014/03/02
144
0

没有更多内容

加载失败,请刷新页面

加载更多

redis系列之——一致性hash算法

一致性hash算法你了解吗?什么时候使用?解决什么问题?redis集群模式使用了一致性hash算法了吗? 数据分片(sharding) 分布式数据存储时,经常要考虑数据分片,避免将大量的数据放在单表或...

诸葛小猿
25分钟前
15
0
IMDB是否提供API? [关闭] - Does IMDB provide an API? [closed]

问题: I recently found a movie organizer application which fetches its data from the IMDB database . 最近,我发现了一个电影管理器应用程序,该应用程序从IMDB数据库中获取其数据。 ...

fyin1314
48分钟前
14
0
Elasticsearch系列之Query DSL

1 前言 我们先通过阅读官方文档,了解一下什么是 Query DSL 。 1.1 Query DSL Elasticsearch provides a full Query DSL (Domain Specific Language) based on JSON to define queries. DSL是......

冯文议
49分钟前
20
0
java使用jsoup时绕过https证书验证

java 代码 增加一个工具类 在jsoup获取之前调用此方法 //your codeSSLHelper.init();Connection connect = Jsoup.connect(url).userAgent(USER_AGENT);connect.header("Accept","text/htm......

MeiJM
52分钟前
30
0
6 Message 消息提示框

1 element.js导入message import { Message } from 'element-ui'# 赋值给变量,便于this调用Vue.prototype.$message = Message 2 调用 this.$message.error('错误')类型有:success,w......

书阳
53分钟前
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部