选择排序法是在要排序的一组数中,选出最小(或最大)的一个数与第一个位置的数交换;在剩下的数当中找最小的与第二个位置的数交换,即顺序放在已排好序的数列的最后,如此循环,直到全部数据元素排完为止
。
选择排序是一种不稳定
排序,比如 [5,8,5,2,9 ], 选择排序的时间复杂度是O(n²),不如冒泡排序,因为冒泡排序最优时间复杂度是O(n),选择排序的另一种变体就是上次研究的堆排序
,时间复杂度降为 O(n * log₂n), 两者一样是通过交换顺序,元素被分为有序区和无序区,一直比较直到无序区元素排完为止。
function selectionSort (arr) {
let minTempIndex = 0
let temp = 0
for(let i = 0; i < arr.length - 1; i++) {
//每一轮都跟无序区第一个元素比
minTempIndex = i
for(let j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[minTempIndex]) {
minTempIndex = j
}
}
//内层每一轮循环完找到最小元素,进行交换操作
//如果无序区第一个元素即最小,就不要交换了
if(minTempIndex != i) {
temp = arr[i]
arr[i] = arr[minTempIndex]
arr[minTempIndex] = temp
}
}
console.log(arr)
}
本文由 dealdot <dealdot#163.com> 创作, Full Stack Developer @ DeepBlue
本文最后编辑时间为: Jun 15, 2021 at 15:53 pm
转载请注明来源