排序-选择排序

选择排序(Selection Sort)是一种简单直观的排序算法。工作原理为:首先在为排序的序列中查找最大(小)元素,存放到排序序列的起始位置,然后再从剩余的序列中查找最大(小)元素放到已经排序序列的末尾。以此类推,直到所有元素均排序完毕。时间复杂度为O(n2)

Selection_sort_animation.gif

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const arr = [17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12]
function selectionSort(arr) {
let minIndex
for (let i = 0 ;i < arr.length - 1;i ++) {
minIndex = i
for (let j = i + 1; j < arr.length;j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j
}

}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
}
return arr
}
console.log(selectionSort(arr)) // 输出[1, 11, 12, 12, 14,14, 17, 20, 20, 23,25, 81]