Algorithms

合併排序是一種使用「分治法」概念的排序算法。 給定一個數組，我們首先將其分為兩個數組。 然後我們遞歸執行此操作，直到獲得只有一個元素的數組。 然後，我們從頭開始構建有序數組，通過對獲得的個別元素進行排序。 假設我們的數組是： [4, 3, 1, 2] 我們首先將數組分成兩個： [4, 3] [1, 2] 然後我們遞歸地分割這些數組： [4] [3] 和 [1] [2] 然後，通過首先對這些元素對進行排序，我們開始構建結果： [3, 4] [1, 2] 然後我們將這兩個數組合併： [1, 2, 3, 4] 讓我們再舉一個具有更多項的數組的例子，這次使用字母： ['e', 'g', 'a', 'd', 'f', 'c', 'b'] 我們將數組分成兩部分： ['e', 'g', 'a'] ['d', 'f', 'c', 'b'] 然後我們將第一個數組再分成兩部分： ['e'] ['g', 'a'] 然後分割第二個結果： ['g'] ['a'] 我們現在取原始數組的第二部分，再分成兩個： ['d', 'f'] ['c', 'b'] 我們分割兩個項目： ['d'] ['f'] ['c'] ['b'] 現在，我們有一系列只有一個元素的數組： ['e'] ['g'] ['a'] ['d'] ['f'] ['c'] ['b'] 現在，我們將它們按成對排序：...

二分搜尋是假設要搜尋的陣列（或其他資料結構）已經排序完成。 我們從陣列和要搜尋的項目開始。 我們查看陣列的中間。我們將元素數量除以2，想像一下左邊有一部分陣列，右邊有另一部分。 如果我們的項目比正在尋找的項目小，那麼它一定在右邊的部分，因此我們可以完全捨棄右邊的部分。 然後我們執行相同的操作，將陣列的右半部分除以2，查看中間的項目，並且我們捨棄陣列的一部分。 最後，你將得到該項目（如果沒有找到該項目，將返回null）。 最後，如果陣列有8個項目，我們在最壞的情況下將在最多4步內找到該項目。 如果陣列有32個項目，在最壞的情況下我們最多需要6步。相較於線性搜尋的32步，這是一個巨大的優化！ 二分搜尋的時間複雜度為O(log n)。 以下是一種可能的實現方式： const binarySearch = (list, item) => { let low = 0 let high = list.length - 1 while (low <= high) { const mid = Math.floor((low + high) / 2) const guess = list[mid] if (guess === item) { return mid } if (guess > item) { high = mid - 1 } else { low = mid + 1 } } return null //如果未找到 } 這如何運作？我們得到list陣列和要搜尋的項目值。然後我們最初將low值設置為0，並將high值設置為陣列的最後一個索引。我們首先查看中間項目，如果它就是我們正在尋找的項目，我們將返回它，並結束。如果不是，我們將low或high值設置為只查看陣列的左半部分或右半部分，並且重複這個過程直到找到該項目。...

快速排序是比選擇排序更有效率的搜尋演算法，它利用了遞迴的概念。 遞迴表示我們在同一函式中呼叫了該函式本身。這是一種非常有用的技巧，在某些情況下很適用，而這正是其中之一。 我說“在大多數情況下”，是因為正如我們將看到的，最壞的情況下，泡沫排序所需要的時間可能與選擇排序相同：O(n^2)。但在最佳情況下，它的運行時間會是O(n log n)，落在O(n)和O(n^2)之間。 它是如何運作的呢？給定一個數組，我們選擇一個項目作為主軸。然後將比主軸小的項目和比主軸大的項目分開。 接著我們對組成比主軸小和比主軸大的項目的兩個數組進行相同的操作。 通過代碼來看會更容易理解： const quickSort = (originalList) => { const list = [...originalList] if (list.length < 2) { return list } const pivot = list[0] const smaller = list.filter((item) => item < pivot) const bigger = list.filter((item) => item > pivot) return [...quickSort(smaller), pivot, ...quickSort(bigger)] } 在這個例子中，我選擇將主軸設置為數組中的第一個項目，但也可以選擇中間的項目，例如： const pivot = list[Math.floor(list.length / 2)] 注意我們首先複製了數組，所以調用quickSort()不會修改原始數組，它只會返回一個新的排序過的數組： const a = [1, 6, 3, 4, 5, 1, 0, 4, 8] console....

線性搜索，也被稱為順序搜索或簡單搜索，是最基本的搜索演算法。給定一個資料結構，例如一個數組，我們通過查看所有元素來搜索某個項目，直到找到為止。 它的實現非常簡單： const linearSearch = (list, item) => { for (const [i, element] of list.entries()) { if (element === item) { return i; } } }; 這會返回我們要查找的項目的索引。例如： linearSearch(['a', 'b', 'c', 'd'], 'd'); //3（索引從0開始） 如果我們查找的是’a’，該演算法只會查看第一個元素並返回，所以速度非常快。 但是如果我們查找的是最後一個元素，該演算法需要遍歷整個數組。計算大O值時，我們始終考慮最壞情況。 因此，該演算法的時間複雜度（演算法複雜度）為O(n)。