x-note
Search…
选择排序
选择排序(Selection Sort)每次从未排序的序列中找出最小(大)的元素,然后放入排序序列的末尾,然后继续寻找最小(大)大元素。
  • 平均时间复杂度:
    O(n2)O(n^2)
  • 最好时间复杂度:
    O(n2)O(n^2)
  • 最坏时间复杂度:
    O(n2)O(n^2)
  • 空间复杂度:
    O(1)O(1)
  • 稳定性:不稳定
  • 排序方式:原地(In-place)
选择排序的主要优势是,每次交换一对元素,至少有一个被移动到其最终位置上。
具体实现:
1
function swap(arr, i, j) {
2
let tmp = arr[i];
3
arr[i] = arr[j];
4
arr[j] = tmp;
5
}
6
7
function selectSort(arr) {
8
const len = arr.length;
9
for (let i = 0; i < len; ++i) {
10
let minIndex = i;
11
for (let j = i; j < len; ++j) {
12
if (arr[i] > arr[j]) {
13
minIndex = j;
14
}
15
}
16
if (i !== minIndex) {
17
swap(arr, i, minIndex);
18
}
19
}
20
return arr;
21
}
Copied!
Copy link