文档章节

java插入排序

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

一、基本概念

      插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为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 通配符的应用— java 排序算法

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

天地一MADAO_
2014/03/02
0
0
程序员必知的8大排序(java实现)

8种排序之间的关系:  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好...

小帅帅丶
2015/01/09
0
7
java或js,ajax或jquery分页代码吗最好就是含有一些高级的算法来分页,

谁有更好的java或js,ajax或jquery分页代码吗最好就是含有一些高级的算法来分页,S2SH框架使用 1 分钟前Thomas8sky | 分类:JAVA相关 | 浏览1次 最近想学会优化代码,学习一些高级的算法,来提...

天池番薯
2014/02/23
323
1
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

IceRainYWC
2014/03/17
0
0
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

闫三
2012/05/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Android 报错 Could not find com.android.tools.build:aapt2:3.2.1-4818971.

报错信息: Could not find com.android.tools.build:aapt2:3.2.1-4818971.Searched in the following locations: file:/C:/Users/96110/AppData/Local/Android/Sdk/extras/m2reposito......

lanyu96
15分钟前
0
0
我的Linux系统九阴真经

我的Linux系统九阴真经 在今天,互联网的迅猛发展,科技技术也日新月异,各种编程技术也如雨后春笋一样,冒出尖来了。各种创业公司也百花齐放百家争鸣,特别是针对服务行业,新型互联网服务行...

linuxCool
58分钟前
19
0
Python程序员需要知道的30个技巧

1 直接交换两个数字位置 1x, y = 10, 202print(x, y)3x, y = y, x4print(x, y)5#1 (10, 20)6#2 (20, 10) 2 比较运算符的链接 1n = 102result = 1 < n < 203print(result)4# True5result = 1 ......

糖宝lsh
58分钟前
11
0
[LintCode] Linked List Cycle(带环链表)

描述 给定一个链表,判断它是否有环。 样例 给出 -21->10->4->5, tail connects to node index 1,返回 true。 这里解释下,题目的意思,在英文原题中,tail connects to node index 1 表示的...

honeymose
今天
10
0
Nginx平滑添加模块

Nginx已经编译安装并运行了一段时间, 然后某一天, 发现需要用到某个模块但当初没有编译, 这个时候怎么办呢? 卸载重新安装肯定可以的, 如果Nginx版本没有变更的话, 则有一个相对平滑的方法来添...

老菜鸟0217
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部