前端工程師演算法（一）
演算法是指解題方案的準確而完整的描述，是一系列解決問題的清晰指定，演算法代表著用系統的方法描述解決問題的策略機制。這個解釋來源於百度，對於入門來說這個解釋等於白說了，你的一臉懵逼我懂，大神略過。
- 說人話
- 演算法
- 你需要了解的演算法是什麼？
開始瞭解演算法就應該對程式有一些認識和理解了，其實我們所有的程式可以理解為演算法加資料結構。撇開資料結構不談，我們日常寫的程式碼如if-else、for(...)等就是演算法。在數學裡加減乘除是演算法，方程公式，幾何公式，乃至高數也都是演算法，而我們的if-else、for(...)就相當於數學中的加減乘除這種級別的演算法，當然在程式裡也有加減乘除，同樣也是演算法。
但是我們日常所表達的演算法和演算法通常的說法有一些區別，我們日常表達的演算法基本上都是特指一些特殊的演算法，這些特殊的演算法就相當於數學中的高數級別（不是指難度）。這些演算法的特殊性並非其難度，而是具備通用性、高效(空間和時間)、解決特定問題的程式。
前端常用演算法之陣列查重演算法
在前端程式設計中查重是比較常見的應用，以陣列查重為例，通常的思路是通過巢狀迴圈，讓每個值與其他每個值進行逐個對比。思路有了，我們就來實現以下：
var arr = [8,4,79,38,2,67,4,19,8,13,47,68,37,13,48,2];
var cont = 0;//記錄比較次數
for(var i = 0; i < arr.length; i++){
for(var j = 0; j < arr.length; j++){
if(arr[i] == arr[j] && i != j){//'i != j'-->排除與自己比較
console.log(arr[i]);
}
cont ++;//累計
}
}
console.log(cont);//256
這個查重演算法可以說基本就實現了，因為解決了特定問題：找到重複的元素。但是這個演算法並不是我們真正需要的演算法，因為這樣對比出現了很多重複，浪費很多計算資源和時間，所以這個演算法需要改進。
改進的目的就是消除重複對比，從陣列的有序性我們可以知道，每一次內部迴圈不需要從頭開始對比，因為前面已經對比過了，所以改進程式碼如下：
for(var i = 0; i < arr.length; i++){
for(var j = i + 1; j < arr.length ; j++){//i+1表示自身和自身之前的元素都不需要比較了
if(arr[i] == arr[j]){
console.log(arr[i]);
}
cont ++;//累計
}
}
console.log(cont);//120
這樣改進後的查重效率可以從對比次數看到，減少了一半多，也就說明了改進後的查重演算法效率提高了一倍多。在演算法中，不存在對錯的概念，而是在保證實現功能的最優方案是什麼。這些最優方案就是我們需要的演算法，這些演算法可以提高使用者的體驗，減少硬體資源的消耗。
用這樣的思路我們來實現以下 陣列去重演算法 ：（這段程式碼摺疊，大家可以先嚐試自己寫）
function unique(arr){
var obj = {};
var result = [];
for(var i in arr){
if(!obj[arr[i]]){
obj[arr[i]] = true;
result.push(arr[i]);
}
}
return result;
}
陣列去重
演算法入門之經典的排序演算法詳解
- 氣泡排序
- 選擇排序
這裡暫時介紹兩種排序演算法，就這兩種排序演算法介紹一些關於排序的應用場景解析，在前面的查重和去重演算法中我們主要考慮到了效率。接著我們用這兩個排序演算法來將演算法的解決特定問題引述出來，這兩個演算法並不能全面說明什麼是特定的問題，它們僅僅只能告訴我們不同的演算法存在其優點和缺點，適應的場景也就會隨之發生變化，而這些場景往往來自不同的業務和功能的需求，需求來源不同，但可以根據其不同特性歸類從而選擇不同的演算法，這就是演算法的通用性。
1.氣泡排序（升序）：
for(var j = 0; j < arr.length - 1; j++){
for(var i = 0; i < arr.length - j - 1; i++){
if(arr[i] > arr[i + 1]){
var temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
首先我們就這這個升序的氣泡排序演算法做一個圖解，來理解氣泡排序的邏輯及其原理：
假設有陣列：var arr = [5,3,7,2,8,6,1,9,4];
當外層迴圈第一次時：j == 0, i == 0。
通過一次外層迴圈，圖解內部完全迴圈，可以看到冒泡迴圈就是通過兩個相鄰元素兩兩比較，升序就是將大值交換到後面的邏輯，每一次外層迴圈都可以獲得對應迴圈終點的最大值。既然是兩兩比較，那麼最一個單獨的元素就不需要在迴圈比較了，所以外層迴圈也可以減去一次。
2.選擇排序（升序）：
for(var j = 0; j <arr.length - 1; j ++){
var max = 0;
for(var i = 0; i < arr.length - j - 1; i++){
if (arr[i + 1] > arr[max]) {
max = i + 1;
}
}
var temp = arr[arr.length - j -1];
arr[arr.length - j - 1] = arr[max];
arr[max] = temp;
}
選擇排序的邏輯就是外層負責交換，內層負責找到對應一次外層迴圈終點內的最大值的索引，然後在一次外層迴圈結束時，將最大值與該次迴圈終點的元素進行交換位置。下面提供選擇排序的圖解：
假設有陣列：var arr = [5,3,7,2,8,6,1,9,4];
-
第一輪外層迴圈
i [i+1]>[max] max
0 3>5 =>false 0
1 7>5 =>true 2
2 2>7 =>false 2
3 8>7 =>true 4
4 6>8 =>false 4
5 1>8 =>false 4
6 9>8 =>true 7
7 4>9 =>false 7
max=7；終點=8；
-
第二輪外層迴圈
i [i+1]>[max] max
0 3>5 =>false 0
1 7>5 =>true 2
2 2>7 =>false 2
3 8>7 =>true 4
4 6>8 =>false 4
5 1>8 =>false 4
6 4>8 =>false 4
max=4；終點=7；
-
第三輪外層迴圈
i [i+1]>[max] max
0 3>5 =>false 0
1 7>5 =>true 2
2 2>7 =>false 2
3 4>7 =>false 2
4 6>7 =>false 2
5 1>7 =>false 2
max=2；終點=6；
-
第四輪外層迴圈
i [i+1]>[max] max
0 3>5 =>false 0
1 1>5 =>false 0
2 2>5 =>false 0
3 4>5 =>false 0
4 6>5 =>true 5
max=5；終點=5；
-
第五輪外層迴圈
i [i+1]>[max] max
0 3>5 =>false 0
1 1>5 =>false 0
2 2>5 =>false 0
3 4>5 =>false 0
max=0；終點=4；
-
第六輪外層迴圈
i [i+1]>[max] max
0 3>4 =>false 0
1 1>4 =>false 0
2 2>4 =>false 0
max=0；終點=3；
-
第七輪外層迴圈
i [i+1]>[max] max
0 3>2 =>true 1
1 1>3 =>false 1
max=1；終點=2；
-
第八輪外層迴圈
i [i+1]>[max] max
0 1>2 =>false 0
max=0；終點=1；
通過上圖將選擇排序的處理邏輯視覺化展示後，可以看到交換次數明顯少於氣泡排序，但是藉助了一個最大值索引變數來完成，這個變數會在每次外層迴圈時被建立，從這個角度來說對於空間的需求比氣泡排序要大。從效率的角度來講選擇排序的空間效率是肯定弱於氣泡排序，但是時間效率會如何呢？這個問題需要考慮更多的因素才能得到結果，由於這篇部落格是基於入門級別的角度來闡述，所以暫時不探討太深入的問題。
通過兩個排序演算法我們可以瞭解到解決同一個問題有多種方案，但是不同方案會有不同的優勢和劣勢，怎麼在實際問題中應用這兩個演算法，需要對它們的優勢和劣勢進行深入的分析，這不在入門的範圍內，後期會有部落格更新演算法知識點的深入理解部分。這篇部落格旨在介紹演算法是什麼？我們如何對具體問題進行分析及編寫演算法，所以上面的兩個排序演算法還並不是我們能拿來解決具體問題的工具，我們還需要對其進一步邏輯分析和封裝，修改成可以在需要是隨時使用的函式。
- 排序演算法需要做的核心工作是什麼？
- 排序演算法都有什麼共同的特點？
這兩個問題其實是一個問題，排序演算法的核心工作就是 【比較+交換】 ，這也是排序演算法的共同特點，所以根據這個核心工作原理，上面兩個排序演算法可以封裝成以下具體方法：
//比較
function compare(a,b){
if (a > b) {
return true;
}else{
return false;
}
}
//交換
function exchange(arr,m,n){
var temp = arr[m];
arr[m] = arr[n];
arr[n] = temp;
}
//封裝氣泡排序
function bubbleSort(arr){
for(var j = 0; j < arr.length - 1; j++){
for(var i = 0; i < arr.length - j - 1 ; i++){
if(compare(arr[i] , arr[i + 1])){
exchange(arr,i,i+1)
}
}
}
}
//封裝選擇排序
function selectionSort(arr){
for(var j = 0; j <arr.length - 1; j ++){
var max = 0;
for(var i = 0; i < arr.length - j - 1; i++){
if(compare(arr[i +1] , arr[max])){
max = i + 1;
}
}
exchange(arr,arr.length - j -1,max);
}
}
瞭解到這裡，我們應該可以大概的理解演算法的定義了：演算法是指解題方案的準確而完整的描述，是一系列解決問題的清晰指定，演算法代表著用系統的方法描述解決問題的策略機制。對於同一個問題我們又會有不同的策略機制，就拿排序演算法來說，我們分析的就有兩種了，但是並不止這兩種，常見的排序演算法還有快速排序、直接插入排序、希爾排序、堆排序、歸併排序、基數排序。不同的排序演算法有不同的應用場景，有時間再來更新深入分析演算法的內容了，今天是大年初四，在這裡祝福大家豬年好運，身體健康，豬定幸福！
想深入瞭解演算法的話可以先參考這兩個部落格：