選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法看蚜。它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最谢癫（或最大）的一個(gè)元素，存放在序列的起始位置失乾，然后再?gòu)氖Ｓ嗟奈磁判蛟刂袑ふ业阶钚常熙。ù螅┰兀缓蠓诺揭雅判虻男蛄械哪┪布钭隆Ｒ源祟愅坡阄溃钡饺看判虻臄?shù)據(jù)元素的個(gè)數(shù)為零。選擇排序是不穩(wěn)定的排序方法纽竣。
算法思路
- 使用線性查找當(dāng)前待排序數(shù)據(jù)墓贿，找到最小值
- 把最小值移動(dòng)到數(shù)組最左邊
- 重復(fù)1、2步蜓氨，直到數(shù)組全部完成排序
代碼實(shí)現(xiàn)
方式一：
使用遞歸實(shí)現(xiàn)聋袋，一次循環(huán)比較好讀，容易理解穴吹，但效率較循環(huán)低一些
const unsort = [6, 1, 7, 8, 9, 3, 5, 4, 2]
const selectedSort = (arr, index = 0) => {
let min = arr[index]
const len = arr.length
for (let i = index; i < len; i++) {
const temp = arr[i]
if (temp < min) {
arr[index] = temp
arr[i] = min
min = temp
}
}
if (index === len - 1) {
return arr
}
return selectedSort(arr, index + 1)
}
const sorted = selectedSort(unsort)
console.log(sorted)
// console: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
方式二：
使用循環(huán)實(shí)現(xiàn)幽勒，兩次循環(huán)，比較不好讀港令，邏輯容易出現(xiàn)紕漏啥容，效率比遞歸要高
const unsort = [6, 1, 7, 8, 9, 3, 5, 4, 2]
const selectedSort = (arr) => {
const len = arr.length
let min
let temp
for (let i = 0; i < len; i++) {
min = arr[i]
temp
for (let j = i + 1; j < len; j++) {
if (arr[j] < min) {
temp = min
min = arr[j]
arr[j] = temp
arr[i] = min
}
}
}
return arr
}
const sorted = selectedSort(unsort)
console.log(sorted)
// console: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
理解
選擇排序使用線性方式來(lái)查找最小值锈颗，所以每次循環(huán)都會(huì)比較n-m(m為循環(huán)次數(shù))個(gè)數(shù)，直到最后一輪只比較一個(gè)數(shù)字咪惠，因此復(fù)雜度是（n - 1）+ (n - 2) + (n - 3) ... + 1 ≈ n2 / 2, 忽略非重要項(xiàng)后為O(n2)
