专栏首页code随笔的专栏详解直接插入排序算法

详解直接插入排序算法

前言

在玩扑克牌的时候,我们抽到一张牌的时候,都是将它插入到当前手中牌的合适位置的。 如下图:

(上图来自算法导论) 直接插入排序也是这样的思想。

基本思想

插入排序的思想是: 将待排序序列分成两个序列,前面的序列保持有序,依次选取后面的序列的元素,在前面的序列中进行插入。 初始时,有序序列的长度为1。

例子

给定序列 [9 , 20 , 13 , 20 , 12 ] 。 初始状态如下:

初始状态

分成两个序列如下:

初始的两个序列

定义两个变量 valindex。其中val表示后面序列中待插入的元素,index表示前面序列中插入的索引。

第一次插入val初始化为 arr[1],即20; 将Index初始化为当前val值的前一个元素的索引,即0;

此时 arr[index] < val 不用移动,index-- 后将变为负数,退出循环。 第一次插入结束。 变成如下状态:

第一趟插入状态1

第二次插入val初始化为 arr[2],即10; 将Index初始化为当前val值的前一个元素的索引,即1;

第二趟插入初始状态

此时 arr[index] > val 并不是合适的插入位置,将index代表的元素向后移动;

第二趟插入状态1

index--;

此时 arr[index] < val 找到了插入位置,即 index + 1; 退出当前循环; 将 arr[index+1] 赋值为val; 得到如下状态图:

第二趟插入状态3

第三次插入val初始化为 arr[3],即13; 将Index初始化为当前val值的前一个元素的索引,即2;

此时 arr[index] > val 并不是合适的插入位置,将index代表的元素向后移动;

得到如下状态图:

index--;

第三趟插入状态2

此时 arr[index] < val 找到了插入位置,即 index + 1; 退出当前循环; 将 arr[index+1] 赋值为val; 得到如下状态图:

第三趟插入状态3

第四趟插入

第四趟插入1

第四趟插入2

代码

先定义变量;

int value;//待插入元素
int index;//初始值为待插入元素前一个元素的索引

由算法思想和例子解释,写成最终代码如下:

import java.lang.reflect.Array;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        InsertSort(new int[] { 9 ,20 , 10, 13 , 12});
    }
    public static void InsertSort(int [] arr){
        int value;//待插入元素
        int index;//初始值为待插入元素前一个元素的索引

        for(int i= 1 ; i< arr.length;i++){
            //i从第二个元素开始,默认第一个元素是有序的
            //循环条件是小于数组长度,因为也要将最后一个元素插入到前面的序列
            value = arr[i];
            index = i - 1;//初始为前一个元素
            while(index >=0 && value < arr[index]){
                //需要保证index合法
                //每当前面的元素比待插入元素大,就向后移动
                arr[index + 1] = arr[index];
                //不用怕覆盖,因为value保存着待插入的值
                index--;
            }
            //当退出循环,表明已经找到了待插入位置,即index + 1
            arr[index + 1] = value;
        }

        System.out.println(Arrays.toString(arr));
    }
}

时间复杂度

在排序前元素已经是按需求有序了,每趟只需与前面的有序元素序列的最后一个元素进行比较,总的排序码比较次数为n-1,元素移动次数为0。时间复杂度为; 而在最差的情况下,及第i趟时第i个元素必须与前面i个元素都做排序码的比较,并且每做一次就叫就要做一次数据移动,此时的时间复杂度为 ; 所以直接插入排序的时间复杂度为。

稳定性

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。如果碰见一个和插入元素相等的,那么将会把待插入元素放在相等元素的后面。所以,相等元素的相对的前后顺序没有改变,所以插入排序是稳定的。

欢迎关注

欢迎大家的关注

扫描下方的二维码或者微信搜一搜即可关注我的微信公众号:code随笔

本文分享自微信公众号 - code随笔(yzsgxhywh),作者:灿烂星空StarrySky

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 希尔排序算法

    当待插入元素是一个很小(当需求是从小到大排序时,从大到小排序时此处为很大)直接插入排序需要移动较多次数,性能会很差。希尔排序解决了这一问题。

    code随笔
  • 详解堆排序算法

    「堆」首先是一个完全二叉树,「堆」分为「大顶堆」和「小顶堆」; 「大顶堆」 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 「小顶堆」同理就是每个节...

    code随笔
  • LeetCode​20题 有效的括号(Valid Parentheses)

    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

    code随笔
  • 【17期】什么情况用ArrayList or LinkedList呢?

    ArrayList中add()方法的性能决定于ensureCapacity()方法。ensureCapacity()的实现如下:

    良月柒
  • JavaScript强化教程——数组的基本处理函数

    本文为 H5EDU 机构官方 HTML5培训 教程,主要介绍:JavaScript强化教程 —— 数组的基本处理函数

    IMWeb前端团队
  • Java集合框架源码解析之LinkedList

    叶志陈
  • 今天,你有微信小游戏提交审核吗?

    12月10日的推文里,写过在未来2个月里,微信小程序应该是要开放了,不然开发者们应该是憋不住了,结果确实都憋不住了。今天微信官方开放了小游戏的能力,同期上线小游...

    企鹅号小编
  • 原 微信小游戏,新的一波商机来袭,你怎么看

    kinbug [进阶者]
  • PyGame Zero:没有样板的游戏 【Gaming】

    Python是一种很好的初学者编程语言。游戏是一个很好的初学者学习的项目:它们是视觉的,自我激励的,向朋友和家人炫耀时是有趣的。然而,用Python编写游戏的最...

    五月Rambo
  • LVS(11)——wrr

    之前建立集群的时候都是wlc策略建立集群(默认方法),它也是一种动态方法,根据权重将新流量分配于被连接数量少的后端真实主机,现在可以尝试修改方法改为wrr策略(...

    gzq大数据

扫码关注云+社区

领取腾讯云代金券