详解直接插入排序

2020年3月30日15:10:27算法评论73阅读模式

前言

在玩扑克牌的时候,我们抽到一张牌的时候,都是将它插入到当前手中牌的合适位置的。
如下图:文章源自随机的未知-https://sjdwz.com/11139.html

详解直接插入排序
(上图来自算法导论)
直接插入排序也是这样的思想。文章源自随机的未知-https://sjdwz.com/11139.html

基本思想

插入排序的思想是:
将待排序序列分成两个序列,前面的序列保持有序,依次选取后面的序列的元素,在前面的序列中进行插入。
初始时,有序序列的长度为1。文章源自随机的未知-https://sjdwz.com/11139.html

例子

给定序列
[9 , 20 , 13 , 20 , 12 ] 。
初始状态如下:文章源自随机的未知-https://sjdwz.com/11139.html

详解直接插入排序
初始状态

分成两个序列如下:文章源自随机的未知-https://sjdwz.com/11139.html

详解直接插入排序
初始的两个序列

定义两个变量 valindex。其中val表示后面序列中待插入的元素,index表示前面序列中插入的索引。文章源自随机的未知-https://sjdwz.com/11139.html

第一次插入
val初始化为 arr[1],即20;
Index初始化为当前val值的前一个元素的索引,即0;
详解直接插入排序文章源自随机的未知-https://sjdwz.com/11139.html

此时 arr[index] < val 不用移动,index-- 后将变为负数,退出循环。
第一次插入结束。
变成如下状态:文章源自随机的未知-https://sjdwz.com/11139.html

详解直接插入排序
第一趟插入状态1

第二次插入
val初始化为 arr[2],即10;
Index初始化为当前val值的前一个元素的索引,即1;文章源自随机的未知-https://sjdwz.com/11139.html

详解直接插入排序
第二趟插入初始状态

此时 arr[index] > val 并不是合适的插入位置,将index代表的元素向后移动;文章源自随机的未知-https://sjdwz.com/11139.html

详解直接插入排序
第二趟插入状态1

index--;文章源自随机的未知-https://sjdwz.com/11139.html

详解直接插入排序
此时 arr[index] < val 找到了插入位置,即 index + 1;
退出当前循环;
arr[index+1] 赋值为val;
得到如下状态图:文章源自随机的未知-https://sjdwz.com/11139.html

详解直接插入排序
第二趟插入状态3

第三次插入
val初始化为 arr[3],即13;
Index初始化为当前val值的前一个元素的索引,即2;
详解直接插入排序文章源自随机的未知-https://sjdwz.com/11139.html

此时 arr[index] > val 并不是合适的插入位置,将index代表的元素向后移动;文章源自随机的未知-https://sjdwz.com/11139.html

得到如下状态图:
详解直接插入排序文章源自随机的未知-https://sjdwz.com/11139.html

index--;文章源自随机的未知-https://sjdwz.com/11139.html

详解直接插入排序
第三趟插入状态2

此时 arr[index] < val 找到了插入位置,即 index + 1;
退出当前循环;
arr[index+1] 赋值为val;
得到如下状态图:文章源自随机的未知-https://sjdwz.com/11139.html

详解直接插入排序
第三趟插入状态3

第四趟插入文章源自随机的未知-https://sjdwz.com/11139.html

详解直接插入排序
第四趟插入1
详解直接插入排序
第四趟插入2

代码

先定义变量;文章源自随机的未知-https://sjdwz.com/11139.html

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

由算法思想和例子解释,写成最终代码如下:文章源自随机的未知-https://sjdwz.com/11139.html

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

public class Solution {
    public static void main(String[] args) {
        InsertSort(new int[] { 9 ,20 , 1013 , 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个元素都做排序码的比较,并且每做一次就叫就要做一次数据移动,此时的时间复杂度为 ;
所以直接插入排序的时间复杂度为。文章源自随机的未知-https://sjdwz.com/11139.html

稳定性

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。如果碰见一个和插入元素相等的,那么将会把待插入元素放在相等元素的后面。所以,相等元素的相对的前后顺序没有改变,所以插入排序是稳定的。文章源自随机的未知-https://sjdwz.com/11139.html

欢迎关注

欢迎大家的关注文章源自随机的未知-https://sjdwz.com/11139.html

扫描下方的二维码关注我的微信公众号:code随笔
详解直接插入排序文章源自随机的未知-https://sjdwz.com/11139.html

文章源自随机的未知-https://sjdwz.com/11139.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
算法最后更新:2022-2-24
  • 本文由 发表于 2020年3月30日15:10:27
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11139.html
算法

详解堆排序

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

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定