一個(gè)算法只是一個(gè)把確定的數(shù)據(jù)結(jié)構(gòu)的輸入轉(zhuǎn)化為一個(gè)確定的數(shù)據(jù)結(jié)構(gòu)的輸出的function。算法內(nèi)在的邏輯決定了如何轉(zhuǎn)換。

基礎(chǔ)算法

一、排序

1、冒泡排序

//冒泡排序function bubbleSort(arr) {

? for(var i = 1, len = arr.length; i < len - 1; ++i) {

? ? for(var j = 0; j <= len - i; ++j) {? ?

? ? ? if (arr[j] > arr[j + 1]) {? ?

? ? ? ? let temp = arr[j];

? ? ? ? arr[j] = arr[j + 1];

? ? ? ? arr[j + 1] = temp;

? ? ? }

? ? }

? }

}

2、插入排序

//插入排序 過程就像你拿到一副撲克牌然后對它排序一樣

function insertionSort(arr) {

? var n = arr.length;?

// 我們認(rèn)為arr[0]已經(jīng)被排序，所以i從1開始

? for (var i = 1; i < n; i++) {?

// 取出下一個(gè)新元素，在已排序的元素序列中從后向前掃描來與該新元素比較大小

? ? for (var j = i - 1; j >= 0; j--) {?

? ? ? ? if (arr[i] >= arr[j]) { // 若要從大到小排序，則將該行改為if (arr[i] <= arr[j])即可

? ? ? ? // 如果新元素arr[i] 大于等于 已排序的元素序列的arr[j]，

? ? ? ? // 則將arr[i]插入到arr[j]的下一位置，保持序列從小到大的順序

? ? ? ? arr.splice(j + 1, 0, arr.splice(i, 1)[0]);? ? ?

? ? ? ? // 由于序列是從小到大并從后向前掃描的，所以不必再比較下標(biāo)小于j的值比arr[j]小的值，退出循環(huán)

? ? ? ? break;?

? ? ? } else if (j === 0) {? ? ? ?

? ? ? // arr[j]比已排序序列的元素都要小，將它插入到序列最前面

? ? ? ? arr.splice(j, 0, arr.splice(i, 1)[0]);

? ? ? }

? ? }

? }

? return arr;

}

當(dāng)目標(biāo)是升序排序，最好情況是序列本來已經(jīng)是升序排序，那么只需比較n-1次，時(shí)間復(fù)雜度O(n)。最壞情況是序列本來是降序排序，那么需比較n(n-1)/2次，時(shí)間復(fù)雜度O(n^2)。

所以平均來說，插入排序的時(shí)間復(fù)雜度是O(n^2)。顯然，次方級(jí)別的時(shí)間復(fù)雜度代表著插入排序不適合數(shù)據(jù)特別多的情況，一般來說插入排序適合小數(shù)據(jù)量的排序。

3、快速排序

//快速排序

function qSort(arr) {

? //聲明并初始化左邊的數(shù)組和右邊的數(shù)組

? var left = [], right = [];

//使用數(shù)組第一個(gè)元素作為基準(zhǔn)值

? var base = arr[0];?

//當(dāng)數(shù)組長度只有1或者為空時(shí)，直接返回?cái)?shù)組，不需要排序

? if(arr.length <= 1) return arr;?

//進(jìn)行遍歷

? for(var i = 1, len = arr.length; i < len; i++) {

? ? if(arr[i] <= base) {? ?

? ? //如果小于基準(zhǔn)值，push到左邊的數(shù)組

? ? ? left.push(arr[i]);

? ? } else {? ?

? ? //如果大于基準(zhǔn)值，push到右邊的數(shù)組

? ? ? right.push(arr[i]);

? ? }

? }

? //遞歸并且合并數(shù)組元素

? return [...qSort(left), ...[base], ...qSort(right)];

? ? //return qSort(left).concat([base], qSort(right));}

補(bǔ)充：

在這段代碼中，我們可以看到，這段代碼實(shí)現(xiàn)了通過pivot區(qū)分左右部分，然后遞歸的在左右部分繼續(xù)取pivot排序，實(shí)現(xiàn)了快速排序的文本描述，也就是說該的算法實(shí)現(xiàn)本質(zhì)是沒有問題的。

雖然這種實(shí)現(xiàn)方式非常的易于理解。不過該實(shí)現(xiàn)也是有可以改進(jìn)的空間，在這種實(shí)現(xiàn)中，我們發(fā)現(xiàn)在函數(shù)內(nèi)定義了left/right兩個(gè)數(shù)組存放臨時(shí)數(shù)據(jù)。隨著遞歸的次數(shù)增多，會(huì)定義并存放越來越多的臨時(shí)數(shù)據(jù)，需要Ω(n)的額外儲(chǔ)存空間。

因此，像很多算法介紹中，都使用了原地（in-place）分區(qū)的版本去實(shí)現(xiàn)快速排序，我們先介紹什么是原地分區(qū)算法。

原地（in-place）分區(qū)算法描述

從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），數(shù)組第一個(gè)元素的位置作為索引。

遍歷數(shù)組，當(dāng)數(shù)組數(shù)字小于或者等于基準(zhǔn)值，則將索引位置上的數(shù)與該數(shù)字進(jìn)行交換，同時(shí)索引+1

將基準(zhǔn)值與當(dāng)前索引位置進(jìn)行交換

通過以上3個(gè)步驟，就將以基準(zhǔn)值為中心，數(shù)組的左右兩側(cè)數(shù)字分別比基準(zhǔn)值小或者大了。這個(gè)時(shí)候在遞歸的原地分區(qū)，就可以得到已排序后的數(shù)組。

原地分區(qū)算法實(shí)現(xiàn)

// 交換數(shù)組元素位置

function swap(array, i, j) {

? ? var temp = array[i];

? ? array[i] = array[j];

? ? array[j] = temp;

}

function partition(array, left, right) {

? ? var index = left;

? ? var pivot = array[right]; // 取最后一個(gè)數(shù)字當(dāng)做基準(zhǔn)值，這樣方便遍歷

? ? for (var i = left; i < right; i++) {

? ? if (array[i] <= pivot) {

? ? ? ? swap(array, index, i);

? ? ? ? index++;

? ? }

}

? ? swap(array, right, index);

? ? return index;

? ? }

因?yàn)槲覀冃枰f歸的多次原地分區(qū)，同時(shí)，又不想額外的地址空間所以，在實(shí)現(xiàn)分區(qū)算法的時(shí)候會(huì)有3個(gè)參數(shù)，分別是原數(shù)組array，需要遍歷的數(shù)組起點(diǎn)left以及需要遍歷的數(shù)組終點(diǎn)right。

最后返回一個(gè)已經(jīng)排好序的index值用于下次遞歸，該索引對應(yīng)的值一定比索引左側(cè)的數(shù)組元素小，比所有右側(cè)的數(shù)組元素大。

再次基礎(chǔ)上我們還是可以進(jìn)一步的優(yōu)化分區(qū)算法，我們發(fā)現(xiàn) <=pivot可以改為<pivot,這樣可以減少一次交換

原地分區(qū)版快速排序?qū)崿F(xiàn)

function quickSort(array) {

? ? function swap(array, i, j) {

? ? ? var temp = array[i];

? ? ? array[i] = array[j];

? ? ? array[j] = temp;

? ? }

? ? function partition(array, left, right) {

? ? ? ? var index = left;

? ? ? ? var pivot = array[right]; // 取最后一個(gè)數(shù)字當(dāng)做基準(zhǔn)值，這樣方便遍歷

? ? ? ? for (var i = left; i < right; i++) {

? ? ? ? ? ? if (array[i] < pivot) {

? ? ? ? ? ? ? ? swap(array, index, i);

? ? ? ? ? ? ? ? index++;

? ? ? ? ? }

? ? ? }

? ? ? swap(array, right, index);? ? ? ?

? ? ? return index;

? ? ? }

? ? ? function sort(array, left, right) {? ?

? ? ? ? ? if (left > right) {? ? ? ?

? ? ? ? ? ? ? return;

? ? ? ? }? ? ? ?

? ? ? ? var storeIndex = partition(array, left, right);

? ? ? ? sort(array, left, storeIndex - 1);

? ? ? ? sort(array, storeIndex + 1, right);

? ? }

? ? sort(array, 0, array.length - 1);? ?

? ? return array;

}

二、字符串

1、回文字符串

//判斷回文字符串

function palindrome(str) {

? var reg = /[\W\_]/g;?

? var str0 = str.toLowerCase().replace(reg, "");?

? var str1 = str0.split("").reverse().join("");?

? return str0 === str1;

}

2、翻轉(zhuǎn)字符串

function reverseString(str) {

? return str.split("").reverse().join("");

}

3、字符串中出現(xiàn)最多次數(shù)的字符

function findMaxDuplicateChar(str) {

? var cnt = {}, //用來記錄所有的字符的出現(xiàn)頻次

? ? ? c = ''; //用來記錄最大頻次的字符

? for (var i = 0; i < str.length; i++) {

? ? ? var ci = str[i];? ?

? ? ? if (!cnt[ci]) {

? ? ? cnt[ci] = 1;

? ? } else {

? ? ? cnt[ci]++;

? ? }? ?

? ? ? if (c == '' || cnt[ci] > cnt[c]) {

? ? ? c = ci;

? ? }

? }?

? ? ? console.log(cnt)? return c;

}

三、數(shù)組

1、數(shù)組去重

//數(shù)組去重

function uniqueArray(arr) {

? var temp = [];?

? for (var i = 0; i < arr.length; i++) {

? ? ? if (temp.indexOf(arr[i]) == -1) {

? ? ? temp.push(arr[i]);

? ? }

? }

? ? ? return temp;?

? ? ? //or

? return Array.from(new Set(arr));

}

四、查找

1、二分查找

//二分查找

function binary_search(arr, l, r, v) {

? if (l > r) {?

? ? return -1;

? }?

? var m = parseInt((l + r) / 2);?

? if (arr[m] == v) {?

? ? return m;

? } else if (arr[m] < v) {?

? ? ? return binary_search(arr, m+1, r, v);

? } else {?

? ? ? ? return binary_search(arr, l, m-1, v);

? }

}

將二分查找運(yùn)用到之前的插入排序中，形成二分插入排序，據(jù)說可以提高效率。但我測試的時(shí)候也許是數(shù)據(jù)量太少，并沒有發(fā)現(xiàn)太明顯的差距。。大家可以自己試驗(yàn)一下~（譬如在函數(shù)調(diào)用開始和結(jié)束使用console.time('插入排序耗時(shí)')和console.timeEnd('插入排序耗時(shí)')）

五、樹的搜索/遍歷

1、深度優(yōu)先搜索

//深搜 非遞歸實(shí)現(xiàn)

function dfs(node) {

? var nodeList = [];?

? if (node) {?

? ? var stack = [];

? ? stack.push(node);?

? ? while(stack.length != 0) {?

? ? ? ? var item = stack.pop();

? ? ? nodeList.push(item);? ? ?

? ? ? ? var children = item.children;? ? ?

? ? ? ? for (var i = children.length-1; i >= 0; i--) {

? ? ? ? ? ? stack.push(children[i]);

? ? ? }

? ? }

? }? return nodeList;

}

//深搜 遞歸實(shí)現(xiàn)

function dfs(node, nodeList) {

if (node) {

? ? nodeList.push(node);? ?

var children = node.children;? ?

for (var i = 0; i < children.length; i++) {

? ? ? dfs(children[i], nodeList);

? ? }

? }?

return nodeList;

}

2、廣度優(yōu)先搜索

//廣搜 非遞歸實(shí)現(xiàn)

function bfs(node) {

? ? var nodeList = [];? ?

? ? if (node != null) {? ?

? ? ? var queue = [];

? ? ? queue.unshift(node);? ? ? ?

? ? ? while (queue.length != 0) {? ?

? ? ? ? ? var item = queue.shift();

? ? ? ? ? ? nodeList.push(item);? ? ? ? ? ?

? ? ? ? ? var children = item.children;? ? ? ? ?

? ? ? ? ? ? for (var i = 0; i < children.length; i++)

? ? ? ? ? ? ? ? queue.push(children[i]);

? ? ? ? }

? ? }? ?

? ? ? ? return nodeList;

}

//廣搜 遞歸實(shí)現(xiàn)

var i=0;?

//自增標(biāo)識(shí)符

function bfs(node, nodeList) {?

? if (node) {

? ? ? nodeList.push(node);? ? ?

? if (nodeList.length > 1) {

? ? ? ? bfs(node.nextElementSibling, nodeList); //搜索當(dāng)前元素的下一個(gè)兄弟元素

? ? ? }

? ? ? node = nodeList[i++];

? ? ? bfs(node.firstElementChild, nodeList); //該層元素節(jié)點(diǎn)遍歷完了，去找下一層的節(jié)點(diǎn)遍歷

? ? }? ? return nodeList;

}

高階函數(shù)衍生算法

1、filter去重

filter也是一個(gè)常用的操作，它用于把Array的某些元素過濾掉，然后返回剩下的元素。也可以這么理解，filter的回調(diào)函數(shù)把Array的每個(gè)元素都處理一遍，處理結(jié)果返回false則過濾結(jié)果去除該元素，true則留下來

用filter()這個(gè)高階函數(shù)，關(guān)鍵在于正確實(shí)現(xiàn)一個(gè)“篩選”函數(shù)。

其實(shí)這個(gè)篩選函數(shù)有多個(gè)參數(shù)，filter(function (element, index, self)，演示一個(gè)使用filter去重，像這樣：

var r,

arr = ['apple', 'strawberry', 'banana', 'pear', 'apple', 'orange', 'orange', 'strawberry'];

r = arr.filter(function (element, index, self) {?

? ? return self.indexOf(element) === index;? ? ? ?

//拿到元素，判斷他在數(shù)組里第一次出現(xiàn)的位置，是不是和當(dāng)前位置一樣，

//一樣的話返回true，不一樣說明重復(fù)了，返回false。

});

2、sort排序算法

排序也是在程序中經(jīng)常用到的算法。無論使用冒泡排序還是快速排序，排序的核心是比較兩個(gè)元素的大小。如果是數(shù)字，我們可以直接比較，但如果是字符串或者兩個(gè)對象呢？

直接比較數(shù)學(xué)上的大小是沒有意義的，因此，比較的過程必須通過函數(shù)抽象出來。通常規(guī)定，對于兩個(gè)元素x和y，如果認(rèn)為x < y，則返回-1，如果認(rèn)為x == y，則返回0，如果認(rèn)為x > y，則返回1，這樣，排序算法就不用關(guān)心具體的比較過程，而是根據(jù)比較結(jié)果直接排序。

值得注意的例子：

// 看上去正常的結(jié)果:

['Google', 'Apple', 'Microsoft'].sort(); // ['Apple', 'Google', 'Microsoft'];

// apple排在了最后:

['Google', 'apple', 'Microsoft'].sort(); // ['Google', 'Microsoft", 'apple']

// 無法理解的結(jié)果:

[10, 20, 1, 2].sort(); // [1, 10, 2, 20]

解釋原因

第二個(gè)排序把a(bǔ)pple排在了最后，是因?yàn)樽址鶕?jù)ASCII碼進(jìn)行排序，而小寫字母a的ASCII碼在大寫字母之后。

第三個(gè)排序結(jié)果，簡單的數(shù)字排序都能錯(cuò)。

這是因?yàn)锳rray的sort()方法默認(rèn)把所有元素先轉(zhuǎn)換為String再排序，結(jié)果’10’排在了’2’的前面，因?yàn)樽址?’比字符’2’的ASCII碼小。

因此我們把結(jié)合這個(gè)原理：

var arr = [10, 20, 1, 2];

? ? arr.sort(function (x, y) {? ?

? ? if (x < y) {? ? ? ?

? ? ? ? return -1;

? ? ? ? }? ?

? ? ? ? ? ? if (x > y) {? ? ? ?

? ? ? ? ? ? ? return 1;

? ? ? ? }? ? ? ? return 0;

? ? });?

? ? console.log(arr); // [1, 2, 10, 20]

上面的代碼解讀一下：傳入x，y，如果x<y，返回-1，x與前面排，如果x>y，返回-1，x后面排，如果x=y，無所謂誰排誰前面。

還有一個(gè)，sort()方法會(huì)直接對Array進(jìn)行修改，它返回的結(jié)果仍是當(dāng)前Array，一個(gè)例子：

var a1 = ['B', 'A', 'C'];var a2 = a1.sort();

? ? a1; // ['A', 'B', 'C']

? ? a2; // ['A', 'B', 'C']

? ? a1 === a2; // true, a1和a2是同一對象

更多web前端相關(guān)知識(shí)，請查閱 HTML中文網(wǎng) ??！