2019中高級前端秘籍之算法篇

2019中高級前端秘籍之CSS篇
 2019中高級前端秘籍之JavaScript篇
 2019中高級前端秘籍之瀏覽器篇
 2019中高級前端秘籍之服務端與網絡篇
 2019中高級前端秘籍之算法篇

其實算法方面在前端的實際項目中涉及得并不多芙粱，但還是需要精通一些基礎性的算法赵誓，一些公司還是會有這方面的需求和考核悬荣，建議大家還是需要稍微準備下，這屬于加分題界轩。

1. 五大算法

貪心算法: 局部最優(yōu)解法
分治算法: 分成多個小模塊，與原問題性質相同
動態(tài)規(guī)劃: 每個狀態(tài)都是過去歷史的一個總結
回溯法: 發(fā)現(xiàn)原先選擇不優(yōu)時，退回重新選擇
分支限界法

2. 基礎排序算法

冒泡排序: 兩兩比較

    function bubleSort(arr) {
        var len = arr.length;
        for (let outer = len ; outer >= 2; outer--) {
            for(let inner = 0; inner <=outer - 1; inner++) {
                if(arr[inner] > arr[inner + 1]) {
                    [arr[inner],arr[inner+1]] = [arr[inner+1],arr[inner]]
                }
            }
        }
        return arr;
    }

選擇排序: 遍歷自身以后的元素彻犁，最小的元素跟自己調換位置

function selectSort(arr) {
    var len = arr.length;
    for(let i = 0 ;i < len - 1; i++) {
        for(let j = i ; j<len; j++) {
            if(arr[j] < arr[i]) {
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }
    return arr
}

插入排序: 即將元素插入到已排序好的數組中

function insertSort(arr) {
    for(let i = 1; i < arr.length; i++) {  //外循環(huán)從1開始局待，默認arr[0]是有序段
        for(let j = i; j > 0; j--) {  //j = i,將arr[j]依次插入有序段中
            if(arr[j] < arr[j-1]) {
                [arr[j],arr[j-1]] = [arr[j-1],arr[j]];
            } else {
                break;
            }
        }
    }
    return arr;
}

3. 高級排序算法

快速排序
- 選擇基準值(base)斑响，原數組長度減一(基準值)，使用 splice
- 循環(huán)原數組钳榨，小的放左邊(left數組)舰罚，大的放右邊(right數組);
- concat(left, base, right)
- 遞歸繼續(xù)排序 left 與 right

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;  //遞歸出口
    }
    var left = [],
        right = [],
        current = arr.splice(0,1); 
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < current) {
            left.push(arr[i])  //放在左邊
        } else {
            right.push(arr[i]) //放在右邊
        }
    }
    return quickSort(left).concat(current,quickSort(right));
}

希爾排序：不定步數的插入排序，插入排序
口訣: 插冒歸基穩(wěn)定薛耻，快選堆希不穩(wěn)定

image.png

穩(wěn)定性：同大小情況下是否可能會被交換位置, 虛擬dom的diff营罢，不穩(wěn)定性會導致重新渲染；

4. 遞歸運用(斐波那契數列)：爬樓梯問題

初始在第一級饼齿，到第一級有1種方法(s(1) = 1)饲漾，到第二級也只有一種方法(s(2) = 1)，第三級(s(3) = s(1) + s(2))

function cStairs(n) {
    if(n === 1 || n === 2) {
        return 1;
    } else {
        return cStairs(n-1) + cStairs(n-2)
    }
}

5. 數據樹

二叉樹: 最多只有兩個子節(jié)點
- 完全二叉樹
- 滿二叉樹
  - 深度為 h, 有 n 個節(jié)點缕溉，且滿足 n = 2^h - 1
二叉查找樹: 是一種特殊的二叉樹考传，能有效地提高查找效率
- 小值在左，大值在右
- 節(jié)點 n 的所有左子樹值小于 n证鸥，所有右子樹值大于 n

image.png

遍歷節(jié)點
- 前序遍歷
  - 1. 根節(jié)點
  - 1. 訪問左子節(jié)點僚楞，回到 1
  - 1. 訪問右子節(jié)點，回到 1
- 中序遍歷
  - 1. 先訪問到最左的子節(jié)點
  - 1. 訪問該節(jié)點的父節(jié)點
  - 1. 訪問該父節(jié)點的右子節(jié)點枉层，回到 1
- 后序遍歷
  - 1. 先訪問到最左的子節(jié)點
  - 1. 訪問相鄰的右節(jié)點
  - 1. 訪問父節(jié)點泉褐，回到 1
插入與刪除節(jié)點

6. 天平找次品

有n個硬幣，其中1個為假幣鸟蜡，假幣重量較輕兴枯，你有一把天平，請問矩欠，至少需要稱多少次能保證一定找到假幣?

三等分算法:
- 1. 將硬幣分成3組财剖，隨便取其中兩組天平稱量
  - 平衡，假幣在未上稱的一組癌淮，取其回到 1 繼續(xù)循環(huán)
  - 不平衡躺坟，假幣在天平上較輕的一組，取其回到 1 繼續(xù)循環(huán)

作者：郭東東
鏈接：https://juejin.im/post/5c64d15d6fb9a049d37f9c20
來源：掘金
著作權歸作者所有乳蓄。商業(yè)轉載請聯(lián)系作者獲得授權咪橙，非商業(yè)轉載請注明出處。

最后編輯于：2019.04.11 17:45:06

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者