八大排序入门之直接插入排序O（n^2）

苦于学了忘，忘了学，部门大佬给机会周会每周一道算法题开阔思维，那我只能从最基础的学起来了。该系列一边学码UML加深印象记住简单的算法逻辑，一边回顾算法。。。反正就随便记随便看吧。有时候会总结一下部门出的题也发上来

---

UML练习

InsertSort.png

UMLCODE

@startuml
start
:InsertSort.directInsert(int[] before);
note right
    直接插入,输入乱序数组{2,1,8,5,4}
    左小右大算法
end note
while (int i=1;i<before.length?) is (true)
note right
    外层循环，哨兵会从{1->8->5->4}
    一个个跟前面的对比大小（内层循环）
    所以会循环n-1次(4)
end note
   :int k=i-1;
note right
    设置哨兵预备插入的位置
    当前监控值所在位置-1
    作用域问题，不用j
end note
   :int temp=before[i];
   note right
       临时存储
       当前监控值
       (第一次循环 拿1（before[1]）)
   end note
  while (int j=k;j>=0&&before[j]>temp) is (true)
  note right
      内层循环，一旦哨兵监控的位置（j）
      下标满足正常的>=0
      且 监控值（位置后）比（监控位置）小
      需要移位 （temp 1|2 2 8 5 4）
      再次对比，不满足条件，那就插入Index
      为0的地方吧。但是已经j--
      k-- 所以在外面监控位置回退
      //其实就是整个循环
      保障所有大于监控值的值往后移动

  end note
    :before[j+1]=before[j];
    :j--;
    :k--;
  endwhile (false)
  :before[k+1]=temp;
  note right
  不满足条件
  （k变成-1或者
  已经不满足before[j]）
  监控位置回退

  end note
  :i++;
endwhile (false)
:return before[];

stop
@enduml

直接排序CODE

//默写实现
    public static int[] insertSort2(int [] before){

        for(int i=1;i<before.length;i++){
            int temp=before[i];//哨兵值
            int k=i-1;//哨兵准备插入的前一个位置  预判
            //判断哨兵和前一个位置
            for(int j=k;j>=0&&before[j]>temp;j--){
                before[j+1]=before[j];//哨兵保存着最后的值 相对的后面的值有两个 所以不怕前面的再覆盖 最后再
                k--;//记录哨兵监控位置
            }
            //最后监控的k--的部分不满足before[k]>temp 或者k<0 所以这个时候k+回1
            before[k+1]=temp;
        }

        /**
         *          | 2 1 9 10 5
         *        -----------
         *        1 | 2|2     哨兵1 对比小于2  2 后移
         *      （1 | -1-|2） ->继续判断 k=-1不合理 哨兵归位 k=0 插入哨兵
         *        9 | 1 2|-9-
         *       10 | 1 2 9|-10-   不满足哨兵小于监控处  哨兵归位
         *       5  | 1 2 9 10| 10  满足哨兵小于监控处  哨兵往前，for(满足)哨兵往前   直至
         *     （5  | 1 2 9 9| 10）
         *     （5  | 1 2 -5- 9 |10） -> k=2合理但是不满足哨兵小于监控位置（2） 归位  插入
         *
         *
         */
        return before;
    }