Sorting

合併排序是一種使用「分治法」概念的排序算法。 給定一個數組，我們首先將其分為兩個數組。 然後我們遞歸執行此操作，直到獲得只有一個元素的數組。 然後，我們從頭開始構建有序數組，通過對獲得的個別元素進行排序。 假設我們的數組是： [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'] 現在，我們將它們按成對排序：...

快速排序是比選擇排序更有效率的搜尋演算法，它利用了遞迴的概念。 遞迴表示我們在同一函式中呼叫了該函式本身。這是一種非常有用的技巧，在某些情況下很適用，而這正是其中之一。 我說“在大多數情況下”，是因為正如我們將看到的，最壞的情況下，泡沫排序所需要的時間可能與選擇排序相同：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....

假設我們有一個數字陣列，我們想要按照元素大小對其進行排序。 你可以有一個物件的陣列，並且可以比較物件的屬性，例如按年齡排序或按姓氏的字母順序排序。細節並沒有改變。 我們的做法是：我們選擇第一個項目。然後我們將其與第二個項目進行比較。如果第二個項目比較小，我們將其與第一個項目交換位置。然後，我們將這個第一個項目與陣列中的每個項目進行比較。 一旦我們知道我們有最小的項目，我們將切換到第二個元素，並將其與陣列中的每個項目進行比較，忽略索引為0，因為我們已經知道那是最小值。以此類推，直到陣列的結尾。 正如你所見，這個演算法非常昂貴。它不僅在陣列的每個項目上進行迭代：對於每個項目，它還會再次迭代陣列。 它的時間複雜度是O(n^2)。請注意，嚴格來說，我們比較的項目數量不斷變小，但這在複雜度的大O表示法中並不意味著任何事情。 以下是我們實現的選擇排序算法。 const selectionSort = (originalList) => { //首先我們將陣列複製一份，以避免修改原始陣列，因為在JS中，物件是按引用傳遞的 const list = [...originalList] const len = list.length for (let i = 0; i < len; i++) { let min = i for (let j = i + 1; j < len; j++) { if (list[min] > list[j]) { min = j } } if (min !== i) { //找到了一個新的最小值。與當前元素交換位置 ;[list[i], list[min]] = [list[min], list[i]] } } return list } const listOfNumbers = [1, 6, 3, 4, 5] console....