前端中經(jīng)常出現(xiàn)的算法總結

雖說我們很多時候前端很少有機會接觸到算法，但對算法的理解和掌握是一個優(yōu)秀工程師的評價標準之一，而且當我們面對較為復雜的問題，這些基礎知識的積累可以幫助我們更好的優(yōu)化解決思路。在一段時間的學習之后，我總結羅列了前端中常見見的幾個算法：

一：排序算法

排序算法是比較開發(fā)的算法之一，方法種類較多，在此列舉兩種簡單的排序算法：冒泡排序和快速排序。冒泡排序其實就是通過比較相鄰位置的元素大小，如果左邊比右邊大，就交換位置，繼續(xù)比較，實際上就是每輪比較都得出一個最大值（或者最小值）。然后通過n-1輪比較，就能得出一個排好序的序列（通過設置一個flag，當數(shù)組基本有序的時候其實不一定需要比較到n-1輪）。

function bubbleSort(arr){
     for(var i=1;i<arr.length;i++){
         for(var j=0;j<arr.length-i;j++){
             var temp;
             if(arr[j]>arr[j+1]){
                 temp=arr[j];
                 arr[j]=arr[j+1];
                 arr[j+1]=temp;
             }
         }
     }
     return arr;
}

快速排序簡單來講就是我們選定一個數(shù)，然后比它小的都放在它左邊，大于等于它的都放在它右邊，那么這個時候對這個數(shù)來講他的位置已經(jīng)排到了正確的地方了，接下來要做的就是在它的左右兩邊分別再進行類似操作。

function quickSort(arr,l,r){
    var i,j,x;
    if(l<r){
        i=l;
        j=r;
        x=arr;
        while(i<j){
            while(i<j&&arr[j]>=x){
                j--;
            }
            if(i<j){
                arr=arr[j];
            }
            while(i<j&&arr<x){
                i++;
            }
            if(i<j){
                arr[j]=arr;
            }
        }
        arr=x;
        //遞歸調(diào)用
        quickSort(arr,i+1,r);
        quickSort(arr,l,i-1);
    }
    return arr;
}


二：階乘算法

function factorialize(num) {
    var result = num;
    if (num < 0) {
        return -1;
    } else if (num === 0 || num === 1) {
        return 1;
    } else {
        while (num > 1) {
            num--;
            result *= num;
        }
    }
    return result;
}


三：回文字符串判斷

如果一個字符串忽略標點符號、大小寫和空格，正著讀和反著讀一模一樣，那么這個字符串就是palindrome(回文)。

function palindrome(str) {
    // 刪除字符串中不必要的字符
    var re = /[W_]/g;
    // 將字符串變成小寫字符
    var lowRegStr = str.toLowerCase().replace(re, '');
    // 如果字符串lowRegStr的length長度為0時，字符串即是palindrome
    if (lowRegStr.length === 0) {
        return true;
    }
    // 如果字符串的第一個和最后一個字符不相同，那么字符串就不是palindrome
    if (lowRegStr[0] !== lowRegStr[lowRegStr.length - 1]) {
        return false;
    } else {
        return palindrome(lowRegStr.slice(1, lowRegStr.length - 1));
    }
}


四：翻轉字符串算法

function reverseString(str) { 
    var tmp = ""; 
    for (var i = str.length - 1; i >= 0; i--) { 
        tmp += str.charAt(i); 
    } 
    return tmp; 
} 
第二種翻轉字符串算法：

function reverseString(s) {
    var arr = s.split('');
    var i = 0, j = arr.length - 1;
    while (i < j) {
        var t = arr;
        arr = arr[j];
        arr[j] = t;
        i++;
        j--;
    }
    return arr.join('');
}


五：整型數(shù)組去重算法

主要考察程序員對Object的使用，利用key來進行篩選。

function unique(arr) 
     var hashTable = {};
     var data = [];
     for(var i = 0, l = arr.length; i < l; i++) {
         if(!hashTable[arr]) {
             hashTable[arr] = true;
             data.push(arr);
         }
     }
     return data;
}

六：數(shù)組中最大差值

function getMaxProfit(arr) {
    var minPrice = arr[0];
    var maxProfit = 0;
    for (var i = 0; i < arr.length; i++) {
        var currentPrice = arr;
        minPrice = Math.min(minPrice, currentPrice);
        var potentialProfit = currentPrice - minPrice;
        maxProfit = Math.max(maxProfit, potentialProfit);
    }
    return maxProfit;
}

七：隨機指定長度字符串

function randomString(n) {
    var str = 'abcdefghijklmnopqrstuvwxyz9876543210';
    var tmp = '';
    var l = str.length;
    for(var i = 0; i < n; i++) {
        tmp += str.charAt(Math.floor(Math.random() * l));
    }
    return tmp;
}

八：統(tǒng)計字符串中次數(shù)最多字母

function findMaxDuplicateChar(str) {
    if(str.length == 1) {
        return str;
    }
    var charObj = {};
    for(var i = 0; i < str.length; i++) {                       
        if(!charObj[str.charAt(i)]) {
            charObj[str.charAt(i)] = 1;
        } else {
            charObj[str.charAt(i)] += 1;
        }
    }
    var maxChar = '',
        maxValue = 1;
    for(var k in charObj) {
        if(charObj[k] >= maxValue) {
            maxChar = k;
            maxValue = charObj[k];
        }
    }
    return maxChar;
}

九：生成菲波那切數(shù)列數(shù)組

斐波那契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學上，斐波納契數(shù)列主要考察遞歸的調(diào)用。通過定義fibo = fibo[i-1]+fibo[i-2];來生成斐波那契數(shù)組。

function getFibonacci(n) {
    var fibarr = [];
    var i = 0;
    while(i < n) {
        if(i <= 1) {
            fibarr.push(i);
        } else {
            fibarr.push(fibarr[i - 1] + fibarr[i - 2])
        }
        i++;
    }
    return fibarr;
}
以上幾個前端中經(jīng)常會出現(xiàn)的小算法是學習中的練習和總結，整理此文如果有錯誤希望小伙伴們積極指正，有更好更簡潔的算法知識也希望不吝分享，以求共同進步。

作者：黑馬程序員前端與移動開發(fā)培訓學院
首發(fā)：http://cloud.itheima.cn/