x-note
Search…
Introduction
FE
正则表达式
Git
基础算法
冒泡排序
插入排序
选择排序
快速排序
归并排序
希尔排序
堆排序
桶排序
计数排序
基数排序
二叉树的遍历
HTTP
Protocol Buffers
gRPC
设计模式
Powered By
GitBook
选择排序
选择排序(Selection Sort)
每次从未排序的序列中找出最小(大)的元素,然后放入排序序列的末尾,然后继续寻找最小(大)大元素。
平均时间复杂度:
O
(
n
2
)
O(n^2)
O
(
n
2
)
最好时间复杂度:
O
(
n
2
)
O(n^2)
O
(
n
2
)
最坏时间复杂度:
O
(
n
2
)
O(n^2)
O
(
n
2
)
空间复杂度:
O
(
1
)
O(1)
O
(
1
)
稳定性:不稳定
排序方式:原地(In-place)
选择排序的主要优势是,每次交换一对元素,至少有一个被移动到其最终位置上。
具体实现:
function
swap
(
arr
,
i
,
j
)
{
let
tmp
=
arr
[
i
];
arr
[
i
]
=
arr
[
j
];
arr
[
j
]
=
tmp
;
}
function
selectSort
(
arr
)
{
const
len
=
arr
.
length
;
for
(
let
i
=
0
;
i
<
len
;
++
i
)
{
let
minIndex
=
i
;
for
(
let
j
=
i
;
j
<
len
;
++
j
)
{
if
(
arr
[
i
]
>
arr
[
j
])
{
minIndex
=
j
;
}
}
if
(
i
!==
minIndex
)
{
swap
(
arr
,
i
,
minIndex
);
}
}
return
arr
;
}
Previous
插入排序
Next
快速排序
Last modified
3yr ago
Copy link