JavaScript算法:選擇排序

假設我們有一個數字數組,並且我們想按元素大小對其進行排序。

您可以有一個對像數組,並且可以比較對象屬性,例如按年齡排序或按姓氏字母排序。細節沒有改變。

我們以這種方式工作:我們選擇第一個項目。然後,我們將其與第二項進行比較。如果第二項較小,我們將其與第一項互換。依此類推,我們將第一個項目與每一個數組中的項目。

知道最小的物品後,我們切換到第二個元素,然後將其與每一個數組中的項目,忽略索引0,因為我們已經知道這是最小值。依此類推,直到數組結束。

如您所見,該算法非常昂貴。它不僅在數組的每個項目上進行迭代:對於每個項目,都再次對數組進行迭代。

它的複雜性是O(n^2)。請注意,從技術上講,我們比較的項目數一直在減少,但這對於復雜性的Big O約定而言並不意味著任何。

這是我們的實現選擇排序

const selectionSort = (originalList) => {
  //we first copy the array to avoid modifying the original array, since objects are passed by reference in 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) {
      // a new minimum is found. Swap that with the current element
      ;[list[i], list[min]] = [list[min], list[i]]
    }
  }
  return list
}

const listOfNumbers = [1, 6, 3, 4, 5] console.log(selectionSort(listOfNumbers)) //[1,3,4,5,6]

免費下載我的JavaScript初學者手冊


更多js教程: