选择排序
选择排序
基本概念
选择排序，英语为 Selection Sort，这是一种简单直观的排序算法，其核心思想在于每次从待排序的数组中选出最小（或最大）的元素，并将其放到数组的起始（或末尾）位置，从而逐步构建有序区间。
它的工作原理是：
- 划分区间：将数组分为两部分：已排序区间 和 未排序区间。初始时已排序区间为空，未排序区间即整个数组。
- 选择最小元素：在未排序区间中，找到最小（或最大）的元素。
- 交换位置：将找到的最小元素与未排序区间的第一个元素交换位置，这样该元素就加入到了已排序区间中。
- 重复操作：对剩余的未排序区间重复上述步骤，直到整个数组排序完毕。
代码实现
function selectionSort(arr) {
const n = arr.length;
// 指向未排序区间的起始位置
for (let i = 0; i < n - 1; i++) {
let minIndex = i; // 假设当前的 i 所对应的数就是最小值
// 内层for循环每次都是从 i 的右侧那一个到最后一个
// 内层for循环的目的是找到最小值的索引
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
// 做一个交换
let temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
const arr = [5, 3, 8, 4, 2];
selectionSort(arr);
console.log(arr);
复杂度
- 时间复杂度：
O(n^2) - 空间复杂度：
O(1)
稳定性
选择排序在每一轮选择中会改变元素的相对顺序，因此选择排序是一种 不稳定 的排序。
我的实现
function sort(arr) {
let index = 0
while(index < arr.length) {
let tar = arr[index]
for(let i = index + 1; i < arr.length; i++) {
if(tar < arr[i]) {
let mid = arr[i]
arr[i] = tar
tar = mid
}
}
arr[index] = tar
index ++
}
return arr
}
function forSort(arr) {
for(i = 0; i < arr.length - 1; i++) {
let tar = arr[i]
for(let j = i + 1; j < arr.length; j++) {
if(tar < arr[j]) {
let mid = arr[j]
arr[j] = tar
tar = mid
}
}
arr[i] = tar
}
return arr
}
console.log(forSort([7,2,5,2,1,7,6,2,0,67,3]))
-EOF-