/

JavaScript算法:選擇排序

JavaScript算法:選擇排序

假設我們有一個數字陣列,我們想要按照元素大小對其進行排序。

你可以有一個物件的陣列,並且可以比較物件的屬性,例如按年齡排序或按姓氏的字母順序排序。細節並沒有改變。

我們的做法是:我們選擇第一個項目。然後我們將其與第二個項目進行比較。如果第二個項目比較小,我們將其與第一個項目交換位置。然後,我們將這個第一個項目與陣列中的每個項目進行比較。

一旦我們知道我們有最小的項目,我們將切換到第二個元素,並將其與陣列中的每個項目進行比較,忽略索引為0,因為我們已經知道那是最小值。以此類推,直到陣列的結尾。

正如你所見,這個演算法非常昂貴。它不僅在陣列的每個項目上進行迭代:對於每個項目,它還會再次迭代陣列。

它的時間複雜度是O(n^2)。請注意,嚴格來說,我們比較的項目數量不斷變小,但這在複雜度的大O表示法中並不意味著任何事情。

以下是我們實現的選擇排序算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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.log(selectionSort(listOfNumbers)) //[1,3,4,5,6]

tags: [“JavaScript”, “algorithm”, “selection sort”, “sorting”]