写点什么

【从 0 到 1 学算法】7. 直接插入排序

作者:Geek_65222d
  • 2022-10-17
    河南
  • 本文字数:972 字

    阅读完需:约 1 分钟

什么是直接插入排序

直接插入排序是基础排序的一种,它的思路是:有一个有序部分,一个无序部分,我们每一次拿无序部分的第一个元素对有序部分 从后往前进行比较(默认升序情况),如果小于则把比较的元素向后移一位 直到大于某个元素 此时把无序元素插入到这个位置。

算法原理

对于数列{9,3,7,2,5,8,1,4}元素进行升序插入排序


初始有序部分 9 无序部分 3 7 2 5 8 1 4


第一趟:3 9 7 2 5 8 1 4,有序 3 9 无序 7 2 5 8 1 4


第二趟:3 7 9 2 5 8 1 4,有序 3 7 9 无序 2 5 8 1 4


第三趟:2 3 7 9 5 8 1 4,有序 2 3 7 9 无序 5 8 1 4


第四趟:2 3 5 7 9 8 1 4,有序 2 3 5 7 9 无序 8 1 4


第五趟:2 3 5 7 8 9 1 4,有序 2 3 5 7 8 9 无序 1 4


第六躺:1 2 3 5 7 8 9 4,有序 1 2 3 5 7 8 9 无序 4


第七趟:1 2 3 4 5 7 8 9,有序 1 2 3 4 5 7 8 9 无序空


可以看出几个问题


1.8 个元素排序 7 趟


2.每次都是让无序部分的第一个元素和有序部分进行从后往前的比较 且比较成功 则有序部分向后移 直到比较不成功则 插入无序元素


3.我们这里排序采用的是有序元素向后移 无序元素插入的方式,比无序元素和有序元素依次交换的时间要少得多这是一个优化点


4.我们在有序部分比较不成功时 直接退出 而不是再继续向前比较,这是个优化点

代码示例

public static void main(String[] args) {    int[] a = {9,3,7,2,5,8,1,4};    int len = a.length;    for (int i=1;i<len;i++){        int j = i-1;        int t = a[i];        System.out.println("第"+(i)+"趟");        while (j>=0){            if (t<a[j]) {                a[j+1]=a[j];            }else {                break;            }            j--;        }        a[++j]=t        for (int k=0;k<len;k++){            System.out.printf("%d ",a[k]);        }        System.out.println();    }}
复制代码


int t 临时变量 记录无序部分的第一个元素,因为后续有序部分向后移会覆盖这个元素

if 判断中:如果无序元素小于有序元素 有序元素向后移 如果无序元素大于等于有序元素 则说明应该插入到此位置 所以这里直接退出 从后向前比较有序 元素 因为最后 j-- 所以需要++才能插入到空出的位置


结果:


第 1 趟


3 9 7 2 5 8 1 4


第 2 趟


3 7 9 2 5 8 1 4


第 3 趟


2 3 7 9 5 8 1 4


第 4 趟


2 3 5 7 9 8 1 4


第 5 趟


2 3 5 7 8 9 1 4


第 6 趟


1 2 3 5 7 8 9 4


第 7 趟


1 2 3 4 5 7 8 9

发布于: 刚刚阅读数: 4
用户头像

Geek_65222d

关注

还未添加个人签名 2022-09-09 加入

还未添加个人简介

评论

发布
暂无评论
【从0到1学算法】7.直接插入排序_十月月更_Geek_65222d_InfoQ写作社区