算法導論學習--學習筆記0527

寫在前面的話

今天開始也要看看

算法導論

這本書了，開個長久的文章記錄一下學習筆記以及感悟，也希望這是一種變相督促自己學習的辦法：）。

之前也讀書的時候算法這裡也隻學過資料結構，但是感覺自己隻學會了部分思想，真要去

leetcode

去刷算法題未免太過吃力，看到别人推薦這本書，就找來了一本pdf版的好好學習一下，希望為時不晚。

封面鎮樓

插入排序

輸入：n個數的一個序列：x1,x2,x3,x4…xn;

輸出：滿足升序排序，要求前面的數字都比後面小

借用原書中的一張圖來代表這個排序的意思

• 圖解：如上圖，撲克牌應該人人都玩過，當拿到n張牌後，你也已經排序好了。如果此時再拿到一張牌，又想讓一手的撲克牌有序，你會選擇怎麼把新拿到的那張牌塞進牌中呢？
• 大多數人辦法是，從後面開始比較，如果第n張牌比想塞的牌大，就往前繼續比較，如果倒數第二張（n-1）還是大，就繼續往前，直到碰到一張

  小

  的牌。如上圖的7插到5後面，而不是10的後面。

用一張圖動态表示(轉自菜鳥教程，侵删)：

放上一個C語言：

void insertion_sort(int arr[], int len){
        int i,j,key;
        for (i=1;i<len;i++){
                key = arr[i];
                j=i-1;
                while((j>=0) && (arr[j]>key)) {
                        arr[j+1] = arr[j];
                        j--;
                }
                arr[j+1] = key;
        }
}
           

Java：

void insertionSort(byte[] array) {
        byte key;
        int j;
        for (int i = 1; i < array.length; i++) {
            key = array[i];
            j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }