苦于學(xué)了忘，忘了學(xué)，部門大佬給機(jī)會(huì)周會(huì)每周一道算法題開闊思維，那我只能從最基礎(chǔ)的學(xué)起來了。該系列一邊學(xué)碼UML加深印象記住簡單的算法邏輯，一邊回顧算法。。。反正就隨便記隨便看吧。有時(shí)候會(huì)總結(jié)一下部門出的題也發(fā)上來

UML練習(xí)

InsertSort.png

UMLCODE

@startuml
start
:InsertSort.directInsert(int[] before);
note right
    直接插入,輸入亂序數(shù)組{2,1,8,5,4}
    左小右大算法
end note
while (int i=1;i<before.length?) is (true)
note right
    外層循環(huán)，哨兵會(huì)從{1->8->5->4}
    一個(gè)個(gè)跟前面的對(duì)比大?。▋?nèi)層循環(huán)）
    所以會(huì)循環(huán)n-1次(4)
end note
   :int k=i-1;
note right
    設(shè)置哨兵預(yù)備插入的位置
    當(dāng)前監(jiān)控值所在位置-1
    作用域問題，不用j
end note
   :int temp=before[i];
   note right
       臨時(shí)存儲(chǔ)
       當(dāng)前監(jiān)控值
       (第一次循環(huán) 拿1（before[1]）)
   end note
  while (int j=k;j>=0&&before[j]>temp) is (true)
  note right
      內(nèi)層循環(huán)，一旦哨兵監(jiān)控的位置（j）
      下標(biāo)滿足正常的>=0
      且 監(jiān)控值（位置后）比（監(jiān)控位置）小
      需要移位 （temp 1|2 2 8 5 4）
      再次對(duì)比，不滿足條件，那就插入Index
      為0的地方吧。但是已經(jīng)j--
      k-- 所以在外面監(jiān)控位置回退
      //其實(shí)就是整個(gè)循環(huán)
      保障所有大于監(jiān)控值的值往后移動(dòng)

  end note
    :before[j+1]=before[j];
    :j--;
    :k--;
  endwhile (false)
  :before[k+1]=temp;
  note right
  不滿足條件
  （k變成-1或者
  已經(jīng)不滿足before[j]）
  監(jiān)控位置回退

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

stop
@enduml

直接排序CODE

//默寫實(shí)現(xiàn)
    public static int[] insertSort2(int [] before){

        for(int i=1;i<before.length;i++){
            int temp=before[i];//哨兵值
            int k=i-1;//哨兵準(zhǔn)備插入的前一個(gè)位置  預(yù)判
            //判斷哨兵和前一個(gè)位置
            for(int j=k;j>=0&&before[j]>temp;j--){
                before[j+1]=before[j];//哨兵保存著最后的值 相對(duì)的后面的值有兩個(gè) 所以不怕前面的再覆蓋 最后再
                k--;//記錄哨兵監(jiān)控位置
            }
            //最后監(jiān)控的k--的部分不滿足before[k]>temp 或者k<0 所以這個(gè)時(shí)候k+回1
            before[k+1]=temp;
        }

        /**
         *          | 2 1 9 10 5
         *        -----------
         *        1 | 2|2     哨兵1 對(duì)比小于2  2 后移
         *      （1 | -1-|2） ->繼續(xù)判斷 k=-1不合理 哨兵歸位 k=0 插入哨兵
         *        9 | 1 2|-9-
         *       10 | 1 2 9|-10-   不滿足哨兵小于監(jiān)控處  哨兵歸位
         *       5  | 1 2 9 10| 10  滿足哨兵小于監(jiān)控處  哨兵往前，for(滿足)哨兵往前   直至
         *     （5  | 1 2 9 9| 10）
         *     （5  | 1 2 -5- 9 |10） -> k=2合理但是不滿足哨兵小于監(jiān)控位置（2） 歸位  插入
         *
         *
         */
        return before;
    }