資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學JavaScript演算法：排序、搜尋和圖遍歷
JavaScript是一種用途廣泛的程式語言，廣泛用於Web開發。雖然它以增強網頁互動性而聞名，但JavaScript也提供了強大的演算法來進行排序、搜尋和圖遍歷。這些演算法對於高效解決複雜問題至關重要。在本文中，我們將探討高階JavaScript演算法，包括快速排序和歸併排序之類的排序演算法、二分查詢之類的搜尋演算法以及廣度優先搜尋和深度優先搜尋之類的圖遍歷演算法。
排序演算法
排序演算法在以特定順序組織資料方面起著至關重要的作用。JavaScript提供了幾種高效的排序演算法，其中兩種是快速排序和歸併排序。
讓我們來看看每種演算法及其在JavaScript中的實現：
快速排序
快速排序是一種流行的分治排序演算法。它的工作原理是選擇一個樞軸元素並將陣列劃分為兩個子陣列，一個子陣列包含小於樞軸的元素，另一個子陣列包含大於樞軸的元素。然後遞迴地將該演算法應用於子陣列。
示例
請考慮以下程式碼：
function quicksort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quicksort(left), pivot, ...quicksort(right)];
}
const arr = [5, 2, 9, 1, 7];
console.log(quicksort(arr));
解釋
在上面的程式碼片段中，quicksort函式接收一個數組作為輸入，並遞迴地應用快速排序演算法。它選擇第一個元素作為樞軸，並建立兩個子陣列left和right，分別儲存小於和大於樞軸的元素。最後，它連線排序後的left陣列、樞軸和排序後的right陣列以返回排序後的陣列。
上述程式碼的輸出將是[1, 2, 5, 7, 9]，這是輸入陣列[5, 2, 9, 1, 7]的排序版本。
歸併排序
歸併排序是另一種高效的排序演算法，它遵循分治方法。它的工作原理是將陣列劃分為較小的子陣列，對它們進行排序，然後將它們合併在一起。
示例
請考慮以下程式碼：
function mergesort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = mergesort(arr.slice(0, mid));
const right = mergesort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const merged = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
merged.push(left[leftIndex]);
leftIndex++;
} else {
merged.push(right[rightIndex]);
rightIndex++;
}
}
return merged.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
const arr = [5, 2, 9, 1, 7];
console.log(mergesort(arr));
解釋
歸併排序函式接收一個數組作為輸入，並遞迴地應用歸併排序演算法。它將陣列分成兩半，並使用歸併排序遞迴地對它們進行排序。merge函式用於透過比較來自兩個陣列的元素並將它們按升序新增到合併陣列中來合併排序後的子陣列。排序後的left和right陣列與任一陣列中剩餘的任何元素連線。
上述程式碼的輸出也將是[1, 2, 5, 7, 9]，這表明歸併排序演算法成功地對輸入陣列進行了排序。
搜尋演算法
搜尋演算法用於在給定資料集中查詢特定元素或條件。最有效的搜尋演算法之一是二分查詢演算法。讓我們探討一下它在JavaScript中的實現：
二分查詢
二分查詢是一種分治演算法，用於在排序陣列中搜索特定元素。它重複地將陣列分成兩半，並將目標元素與中間元素進行比較，以確定應該搜尋左半部分還是右半部分。
示例
請考慮以下程式碼：
function binarySearch(arr, target) {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
const mid = Math.floor((start + end) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
const arr = [1, 2, 5, 7, 9];
console.log(binarySearch(arr, 7));
解釋
binarySearch函式接收一個排序陣列arr和一個目標元素target作為輸入。它初始化兩個指標start和end，分別表示子陣列的起始和結束索引。然後，它進入一個迴圈，該迴圈持續到start指標小於或等於end指標。在每次迭代中，它計算中間索引mid並將目標元素與子陣列的中間元素進行比較。如果找到目標，則返回索引。否則，它根據目標大於還是小於中間元素來調整start和end指標。
上述程式碼的輸出將是3，這表明目標元素7在陣列[1, 2, 5, 7, 9]的索引3處被找到。
圖遍歷演算法
圖遍歷演算法用於探索或遍歷圖資料結構。它們可用於解決各種問題，例如查詢最短路徑或檢測迴圈。兩種常用的圖遍歷演算法是廣度優先搜尋(BFS)和深度優先搜尋(DFS)。讓我們檢查一下它們在JavaScript中的實現。
廣度優先搜尋 (BFS)
廣度優先搜尋是一種演算法，它在移動到下一層之前，探索圖中同一層的所有頂點。它使用佇列來跟蹤接下來要訪問的頂點。
示例
請考慮以下程式碼：
function bfs(graph, start) {
const queue = [start];
const visited = new Set();
while (queue.length > 0) {
const vertex = queue.shift();
if (!visited.has(vertex)) {
console.log(vertex);
visited.add(vertex);
for (const neighbor of graph[vertex]) {
queue.push(neighbor);
}
}
}
}
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'E'],
D: ['B'],
E: ['C']
};
console.log('BFS traversal:');
bfs(graph, 'A');
解釋
bfs函式接收一個以鄰接表表示的圖和一個起始頂點作為輸入。它用起始頂點初始化一個佇列和一個visited集合來跟蹤已訪問的頂點。然後，它進入一個迴圈，該迴圈持續到佇列為空。在每次迭代中，它從佇列中刪除一個頂點，檢查它是否已被訪問，如果未被訪問，則將其標記為已訪問並列印它。然後，它將頂點的所有未訪問的鄰居新增到佇列中。
深度優先搜尋 (DFS)
深度優先搜尋是一種演算法，它透過沿著每個分支儘可能遠地遍歷來探索圖的所有頂點，然後再回溯。它使用堆疊或遞迴來跟蹤接下來要訪問的頂點。
示例
function dfs(graph, start, visited = new Set()) {
console.log(start);
visited.add(start);
for (const neighbor of graph[start]) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'E'],
D: ['B'],
E: ['C']
};
console.log('DFS traversal:');
dfs(graph, 'A');
解釋
dfs函式接收一個以鄰接表表示的圖、一個起始頂點和一個visited集合（可選）作為輸入。它列印當前頂點，將其標記為已訪問，並遞迴地將dfs函式應用於其未訪問的鄰居。此過程持續到所有頂點都被訪問。
405 次瀏覽
