【寒假实习备战day7】直接排序算法的学习

简单的自我介绍

我是一名双非大二学生，目前学习方向为Java后端，快速学习并学到了springboot，并和实验室的朋友做了一个简单的微信小程序，想在寒假找份有关互联网的实习，打算海投，城市和公司暂时没有特别强烈的意向，我会再次牢固的复习一遍Java整套学习知识，并且开始补充算法知识刷算法题，来备战这次寒假实习，并且想报名参加蓝桥杯Java B组的比赛，希望我的一些学习笔记能为你带来一些帮助，这次给大家带来的是直接排序的算法学习。

今天开始再次使用我之前好久没用的时间管理APP 时光序了，今天也可以在动态里可以看见我最新的情况，不能再这样低效的学习下去了，感觉疫情还会持续很长时间，不管是在学校还是以后在工作中，疫情都会影响到我的生活，我应该早些学会积极的去减少这些影响对我造成的损害，不断尝试找到适合自己的方法！如果有同样被疫情所影响的小伙伴们可以尝试一下，用时间管理APP去管理一下自己生活，刚开始做任务要布置的简单一下，万事开头难，撑过最开始最痛苦的时间之后，相信我们能更好的去减少疫情对我们的影响！
什么是直接插入排序

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

算法原理

对于数列{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();
    }
}