JavaScript數據結構和算法

前言

在過去的幾年中，得益于Node.js的興起，JavaScript越來越廣泛地用于服務器端編程。鑒于JavaScript語言已經走出了瀏覽器，程序員發現他們需要更多傳統語言（比如C++和Java）提供的工具。這些工具包括傳統的數據結構（如鏈表，棧，隊列，圖等），也包括傳統的排序和查找算法。本文主要是總結什么情況下使用何種數據結構較好，并沒有細講里面的原理和實現方式，僅僅提供給閱讀過《數據結構和算法》的同學作為總結和參考筆記，如果未細究過數據結構和算法的同學，本文也可以作為一個方向，希望能引導你去深究數據結構和算法。

為什么要學習數據結構和算法

數據結構和算法對于很多前端工程師來說，一直覺得是可有可無的，但其實不然，個人覺得，前端工程師其實是最需要重視數據結構和算法的人，因為前端所做的東西是用戶訪問網站第一眼看到的東西，特別在移動浪潮到來之后，對用戶體驗越來越高，對前端提出了更高的要求，面對越來越復雜的產品，需要堅實的數據結構和算法基礎才能駕馭。
如果沒有學習過計算機科學的程序員，當我們在處理一些問題時，比較熟悉的數據結構就是數組，數組無疑是一個很好的選擇。但很多時候，對于很多復雜的問題，數組就顯得太過簡陋了，當學習了數據結構和算法之后，對于很多編程問題，當想到一個合適的數據結構后，設計和實現解決這些問題的算法就手到擒來。

列表

在日常生活中，人們經常使用列表：待辦事項列表、購物清單、最佳十名榜單等等。而計算機程序也在使用列表，在下面的條件下，選擇列表作為數據結構就顯得尤為有用：

數據結構較為簡單
不需要在一個長序列中查找元素，或者對其進行排序

反之，如果數據結構非常復雜，列表的作用就沒有那么大了。

棧

棧是一種特殊的列表，棧內的元素只能通過列表的一端訪問，這一端稱為棧頂。想象一下，我們平常在飯館見到的一摞盤子就是現實世界常見的棧的例子，只能從最上面取盤子，盤子洗干凈后，也只能放在最上面。棧被稱為一種后入先出的數據結構。是一種高效的數據結構，因為數據只能在棧頂添加或刪除，所以這樣的操作很快。
使用條件：

只要數據的保存滿足后入先出或先進后出的原理，都優先考慮使用棧

images

隊列

隊列也是一種列表，不同的是隊列只能在隊尾插入元素，在隊首刪除元素。想象一下，我們在銀行排隊，排在最前面的人第一個辦理業務，而后面來的人只能排在隊伍的后面，直到輪到他們為止。
使用條件：

只要數據的保存滿足先進先出、后入后出的原理，都優先考慮使用隊列

常見應用場景：

隊列主要用在和時間有關的地方，特別是操作系統中，隊列是實現多任務的重要機制
消息機制可以通過隊列來實現，進程調度也是使用隊列來實現

images

鏈表

鏈表也是一種列表，為什么需要出現鏈表，JavaScript中數組的主要問題時，它們被實現成了對象，與其他語言（比如C++和Java）的數組相對，效率很低。如果你發現數組在實際使用時很慢，就可以考慮使用鏈表來代替它。
使用條件：

鏈表幾乎可以用在任何可以使用一維數組的情況中。如果需要隨機訪問，數組仍然是更好的選擇。

images

字典

字典是一種以鍵-值對行駛存儲數據的數據結構，JavaScript中的Object類就是以字典的形式設計的。JavaScript可以通過實現字典類，讓這種字典類型的對象使用起來更加簡單，字典可以實現對象擁有的常見功能，并相應拓展自己想要的功能，而對象在JavaScript編寫中隨處可見，所以字典的作用也異常明顯了。

散列

散列（也稱為哈希表）是一種的常用的數組存儲技術，散列后的數組可以快速地插入或取用。散列使用的數據結構叫做散列表。在散列表上插入、刪除和取用數據都非常快，但對于查找操作來說卻效率低下，比如查找一組數組中的最大值和最小值。這些操作需要求助于其他數據結構，比如下面介紹的二叉查找樹。

散列表在JavaScript中可以基礎數組去進行設計。數組的長度是預先設定的，所有元素根據和該元素對應的鍵，保存在數組的特定位置，這里的鍵和對象的鍵是類型的概念。使用散列表存儲數組時，通過一個散列函數將鍵映射為一個數字，這個數字的范圍是0到散列表的長度。

即使使用一個高效的散列函數，依然存在將兩個鍵映射為同一個值得可能，這種現象叫做碰撞。常見碰撞的處理方法有：開鏈法和線性探測法（具體概念有興趣的可以網上自信了解）

使用條件：

可以用于數據的插入、刪除和取用，不適用于查找數據

images

圖

圖由邊的集合及頂點的集合組成。地圖是我們身邊很常見的現實場景，比如每兩個城鎮都由某種道路相連。上面的每個城鎮可以看作一個頂點，連接城鎮的道路便是邊。邊由頂點對（v1, v2）定義，v1和v2分別是圖中的兩個頂點。頂點也有權重，也成為成本。如果一個圖的頂點對是有序的，則稱之為有向圖（例如常見的流程圖），反之，稱之為無序圖。
使用場景（用圖對現實中的系統建模）：

交通系統，可以用頂點表示街道的十字路口，邊可以表示街道。加權的邊可以表示限速或者車道的數量。可以用該系統判斷最佳路線及最有可能堵車的街道。
任何運輸系統都可以用圖來建模。比如，航空公司可以用圖來為其飛行系統建模。將每個機場看成頂點，將經過兩個頂點的每條航線看作一條邊。加權的邊可以表示從一個機場到另一個機場的航班成本，或兩個機場間的距離，這取決于建模的對象是什么。

搜索圖的算法主要有兩種：深度優先搜索和廣度優先搜索。

二叉樹和二叉查找樹

樹是計算機科學中經常用到的一種數據結構。樹是一種非線性的數據結構，以分層的方式存儲數據。
二叉樹每個節點的子節點不允許超過兩個。一個父節點的兩個子節點分別稱為左節點和右節點，通過將子節點的個數限定為2，可以寫出高效的程序在樹中插入、查找和刪除數據。
二叉查找樹（BST）是一種特殊的二叉樹，相對較小的值保存在左節點中，較大的值保存在右節點中。這一特性使得查找的效率很高，對于數值型和非數值型的數據，比如單詞和字符串，都是如此。
二叉查找樹實現方法

function Node(data, left, right) { // 創建節點 this.data = data; this.left = left; this.right = right; this.show = show } function show () { // 顯示樹的數據 return this.data } function BST () { // 二叉查找樹類 this.root = null; this.insert = insert; this.inOrder = inOrder; // inOrder是遍歷BST的方式 } function insert (data) { // 向樹中插入數據 var n = new Node(data, null, null) if (this.root == null) { this.root = n; } else { var current = this.root; var parent; while (true) { parent = current if (data < current.data) { current = current.left; if (current == null) { parent.left = n; break; } } else { current = current.right; if (current == null) { parent.right = n; break; } } } } }

images
遍歷BST的方式有三種：中序遍歷（以升序訪問樹中所有節點，先訪問左節點，再訪問根節點，最后訪問右節點）、先序遍歷（先訪問根節點，再以同樣的方式訪問左節點和右節點）、后序遍歷（先訪問葉子節點，從左子樹到右子樹，再到根節點）

排序算法

基本排序算法

基本排序算法，其核心思想是指對一組數組按照一定的順序重新排列。重新排列時用到的技術是一組嵌套的for循環。其中外循環會遍歷數組的每一項，內循環則用于比較元素。

冒泡排序

冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

function bubbleSort (arr) {var i = arr.length; while (i > 0) { var pos = 0 for (var j = 0; j < i; j++) { if (arr[j] > arr[j+1]){ pos = j var temp = arr[j] arr[j] = arr[j+1] arr[j+1] = temp } } i = pos } return arr } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

images

選擇排序

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

function selectionSort (arr) {var len = arr.length; var minIndex, temp; for (var i = 0; i < len-1; i++) { minIndex = i; for (var j = i+1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j } } temp = arr[minIndex] arr[minIndex] = arr[i] arr[i] = temp } return arr } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

images

插入排序

插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

function insertSort (arr) {var len = arr.length for (i = 1; i < len; i++) { var key = arr[i] var j = i - 1 while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j] j--; } arr[j+1] = key } return arr } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(insertSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

images

高級排序算法

高級數據排序算法，通常用于處理大型數據集的最高效排序算法，它們處理的數據集可以達到上百萬個元素，而不僅僅是幾百個或者幾千個，下面我們將介紹希爾排序、歸并排序和快速排序。

希爾排序

1959年Shell發明，第一個突破O(n^2)的排序算法；是簡單插入排序的改進版；它與插入排序的不同之處在于，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。
希爾排序的核心在于間隔序列的設定。既可以提前設定好間隔序列，也可以動態的定義間隔序列。

function shellSort (arr) {var len = arr.length; var temp, gap = 1; while (gap < len /3 ) { gap = gap * 3 + 1 } while (gap >= 1) { for (var i = gap; i < len; i++) { temp = arr[i] for (var j = i - gap; j >= 0 && arr[j] > temp; j-=gap) { arr[j+gap] = arr[j] } arr[j+gap] = temp } gap = (gap - 1) / 3 } return arr } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

5555

歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。歸并排序是一種穩定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。

function mergeSort (arr) {var len = arr.length if (len < 2) { return arr } var middle = Math.floor(len / 2) var left = arr.slice(0, middle) var right = arr.slice(middle) return merge (mergeSort(left), mergeSort(right)); } function merge (left, right) { var result = [] while (left.length && right.length) { if (left[0] < right[0]) { result.push(left.shift()) } else { result.push(right.shift()) } } while (left.length) { result.push(left.shift()) } while (right.length) { result.push(right.shift()) } return result } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(mergeSort(arr));

images

快速排序

快速排序是處理大數據集最快的排序算法之一。它是一種分而治之的算法，通過遞歸的方法將數據依次分解為包含較小元素和較大元素的不同子序列。該算法不斷重復這個步驟知道所有數據都是有序的。
這個算法首先要在列表中選擇一個元素作為基準值。數據排序圍繞基準值進行，將列表中小于基準值的元素移到數組的底部，將大于基準值的元素移到數組的頂部。

function qSort (arr) {if (arr.length == 0) { return [] } var left = [] var right = [] var pivot = arr[0] for (var i = 1; i < arr.length; i++) { if (arr[i] < pivot) { left.push(arr[i]) } else { right.push(arr[i]) } } return qSort(left).concat(pivot, qSort(right)) } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(qSort(arr));

images

檢索算法

在列表中查找數據有兩種方式：順序查找和二分查找。順序查找適用于元素隨機排列的列表；二分查找適用于元素已排序的列表。二分查找效率更高，但是必須在進行查找之前花費額外的時間將列表中的元素排序。

順序查找

對于查找數據，最簡單的方法就是從列表的第一個元素開始對列表元素逐個進行判斷，直到找到了想要的結果，或者直到列表結尾也沒有找到。這種方法稱為順序查找，有時也被稱為線性查找。

function seqSearch (arr, data) {for (var i = 0; i < arr.length; i++) { if (arr[i] == data) { return i; } } return -1; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(seqSearch(arr, 15))

二分查找

二分法查找，也稱折半查找，是一種在有序數組中查找特定元素的搜索算法。查找過程可以分為以下步驟：

首先，從有序數組的中間的元素開始搜索，如果該元素正好是目標元素（即要查找的元素），則搜索過程結束，否則進行下一步。
如果目標元素大于或者小于中間元素，則在數組大于或小于中間元素的那一半區域查找，然后重復第一步的操作。
如果某一步數組為空，則表示找不到目標元素。

function binSearch (arr, data) {var low = 0; var high = arr.length - 1 while (low <= high) { var middle = Math.floor((low + high) / 2) if (arr[middle] < data) { low = middle + 1 } else if (arr[middle] > data) { high = middle - 1 } else { return middle } } return -1 } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(binSearch(arr, 15))