数据结构与算法学习-简单排序算法之插入排序
数据结构与算法学习-简单排序算法之插入排序
freedwang 发表于2年前
数据结构与算法学习-简单排序算法之插入排序
  • 发表于 2年前
  • 阅读 15
  • 收藏 0
  • 点赞 1
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

摘要: 插入排序比冒泡排序和选择排序稍微高级一点,原理也挺简单,值得学习

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

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

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

接着上我自己写的一个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小于当前索引的值做比较,大于当前值的右移一个位置,直到找到那个小于当前值得,将当前数据安插进去就行了,逻辑还是比较简单的。
小结:
算法确实是个磨脑筋的活,一天看的太多也理解不了,只要坚持每天看,总会有收获的,不积跬步无以至千里啊!加油!!!
标签: 插入排序
共有 人打赏支持
粉丝 0
博文 2
码字总数 1358
×
freedwang
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: