文档章节

数据结构与算法学习-简单排序算法之插入排序

freedwang
 freedwang
发布于 2016/04/07 11:52
字数 536
阅读 18
收藏 0

先上一张书上看的图帮助理解

理解插入排序得先理解一个概念,局部有序:就是拿上图来说,有一个被标记的队员,站在被标记人左侧的都是已经有顺序的,站在右边的都是等待被排序的。

怎么排序呢?其实只要右边的人一个个的拿来往左边有序的队员里面安插就行了。先让被标记的那个人出对,这时队伍空出了那个位置,被标记的人依次与左边的人一个个的比较,如果左边的人身高大于被标记的人的身高,则把左边当前比较的这个人往右移一个位置,直到找到比被标记的人身高矮的,那这个位置就是被标记的人应该站的位置,一个比较完成之后将被标记的人右移一位,继续比较,直到最后一个人就行了。

接着上我自己写的一个demo:

package com.freedwang.study.sort;

/**
 * 插入排序
 * Created by wangfei on 2016/4/7.
 */
public class InsertSort {
    private static int[] data = {1,9,3,6,2,4,15,12,18,19,14,11};

    public static void sort() {
        int temp,tempData;

        for (int i=1; i<data.length; i++) {
            tempData = data[i];
            temp = i;

            while (temp>0 && data[temp-1]>tempData) {
                data[temp] = data[temp-1];
                --temp;
            }

            data[temp] = tempData;
        }
    }

    public static void display() {
        for (int i : data) {
            System.out.println(i);
        }
    }

    public static void main(String[] args) {
        sort();
        display();
    }
}
看demo解释,从数组的位置1开始遍历(不是位置0),记录下位置1的索引和值,在while循环中一直与索引大于0小于当前索引的值做比较,大于当前值的右移一个位置,直到找到那个小于当前值得,将当前数据安插进去就行了,逻辑还是比较简单的。
小结:
算法确实是个磨脑筋的活,一天看的太多也理解不了,只要坚持每天看,总会有收获的,不积跬步无以至千里啊!加油!!!

© 著作权归作者所有

共有 人打赏支持
freedwang
粉丝 0
博文 2
码字总数 1358
作品 0
昌平
私信 提问
算法与数据结构(二):排序篇-O(n^2)算法:选择 & 插入算法优化

排序基础 O(n^2)的算法虽然简单,但也实用!让我们从最简单的基础排序算法开始,打开我们的算法大门! 排序算法 O(n^2)的排序算法 最优的时间复杂度为O(nlogn)的算法。 为什么要学习O(n^2)的...

天涯明月笙
2017/09/13
0
0
各种基本算法实现小结(五)—— 排序算法

各种基本算法实现小结(五)—— 排序算法 (均已测试通过) * 选择排序 |____简单选择排序 |____堆排序 |____归并排序 * 交换排序 |____冒泡排序 |____快速排序 * 插入排序 |____直接插入排...

长平狐
2013/01/06
210
0
八种排序算法效率比较

从刚上大一那会儿学的C语言开始,就已经接触到了不少排序算法,但当时都只是为了完成简单的排序任务而已,而且所给的数据也不够多,所以看不出各个排序算法间的执行效率的优劣。最近有个数据...

lwaif
2015/10/22
2.3K
0
一个Java小白通向数据结构算法之旅(7) - 简单排序总结

前言 昨天双,什么也没买。因为没有想到什么必需的用品,何况也没有钱。身为屌丝的我,只能敲敲代码,写一写总结,岂不美滋滋哉。今天看了《五亿探长雷洛》这部电影,非常喜欢刘德华饰演的雷...

cmazxiaoma
2017/11/12
0
0
各种排序算法分析与比较

首先,请允许我用这样的题目来作为本博文的题目,但是目前也想不到其他好的题目,所以就先定为这个题目吧。 排序算法对于数据结构和算法课程来说都是非常重要的内容,在数据结构中,排序算法...

长平狐
2013/12/25
271
0

没有更多内容

加载失败,请刷新页面

加载更多

追加字节能优化性能

这种方式看起来很神奇,单如果深入理解处理器架构就能理解其中的奥秘。让我们先来看看LinkedTransferQueue这个类,它使用一个内部类型来定义队列的头队列Head和尾节点tail,二这个内部类Pad...

无知的小狼
18分钟前
0
0
性能优化(JVM概念及配置)

虚拟机组成 一次编写,到处运行 Java虚拟机是对操作系统的模拟,隔离差异 2018编程语言排行榜 一个复杂的构架 虚拟机的内部概念 运行原理 编译器,解释器执行流程 内存分配-线程模型 栈帧模型...

这很耳东先生
25分钟前
2
0
Scala之初步认识与环境准备

1. 了解 Scala 1.1. 什么是 Scala Scala 是 Scalable Language 的简写,是一门多范式的编程语言。 Scala设计的初衷是要集成面向对象编程和函数式编程的各种特性。Scala运行于Java平台(Java虚...

飞鱼说编程
46分钟前
4
0
Vue项目分环境打包的实现步骤

在项目开发中,我们的项目一般分为开发版、测试版、Pre版、Prod版。Vue-cli的默认环境一只有dev和prod两个,之前每次要发布测试版或Pre版都是修改了源码中API地址后打包,这样很麻烦。如果能...

peakedness丶
46分钟前
6
0
vue+lowdb+express

搭建流程: 1.安装Node.js; 2.安装npm; 3.安装Express; 搭建流程 npm install -g express 安装 express 生成器 npm install -g express-generator 查看是否安装成功,随便输的一个命令...

Js_Mei
52分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部