文档章节

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个元素 
  • 最好情况:正序,不需要移动元素

© 著作权归作者所有

共有 人打赏支持
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中运用数组的四种排序方法

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

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

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

闫三
2012/05/08
0
0
面试 10:玩转 Java 选择排序和插入排序

面试 10:Java 玩转选择排序和插入排序 昨天给大家讲解了 Java 玩转冒泡排序,大家一定觉得并没有什么难度吧,不知道大佬们玩转了吗?不知道大家有没有多加思考,实际上在我们最后的一种思路...

nanchen2251
07/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

移除或自定义 WordPress 仪表盘欢迎面板

第一次登录 WordPress 后台仪表盘页面,默认都会显示 WordPress 的欢迎面板: 如果我们要移除这个面板,在主题的 functions.php 中添加下面的代码即可: 12 //移除 WordPress 仪表盘欢迎面...

james_laughing
18分钟前
0
0
HashMap实现原理及源码分析

HashMap实现原理及源码分析   哈希表(hash table)也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,...

DemonsI
21分钟前
0
0
eggjs学习笔记

快速初始化 生成项目(要求最低的node版本8.x) npm i egg-init -gegg-init egg-example --type=simplecd egg-examplenpm i 启动项目 npm run dev 配置 环境配置会覆盖默认配置 config...

别人说我名字很长
24分钟前
1
0
Winform Timer控件时间间隔

sender as System.Timers.Timer).Interval = 23 * 60 * 60 * 1000.0;//将时间间隔改为23小时,23小时后重新发生timer_Elapsed事件。 //60000:时间间隔1分钟,300000:时间间隔5分钟,600000:...

笑丶笑
25分钟前
0
0
在win10系统下怎样快速切换任务视图

切换窗口:Alt + Tab 任务视图:Win + Tab (松开键盘界面不会消失) 切换任务视图:Win + Ctrl +左/右 创建新的虚拟桌面:Win + Ctrl + D 关闭当前虚拟桌面:Win + Ctrl + F4...

SummerGao
29分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部