·5 分钟阅读·管理员
排序算法-选择排序
选择排序(Selection Sort)是一种简单直观的排序算法。它的基本思想是在未排序序列中找到最小(或最大)的元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(或最大)的元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。选择排序与冒泡排序的时间复杂度是一样的
选择排序
把酒看花想诸弟,杜陵寒食草青青。
排序算法-选择排序
选择排序(Selection Sort)是一种简单直观的排序算法。它的基本思想是在未排序序列中找到最小(或最大)的元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(或最大)的元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
选择排序与冒泡排序的时间复杂度是一样的
选择排序的基本步骤:
- 查找最小值:从未排序的序列中找到最小(或最大)的元素。
- 交换位置:将它与未排序序列的第一个元素交换。
- 缩小未排序区域:将未排序序列的起始位置向右移动一位。
- 重复步骤1-3:直到所有元素都已排序。
- 简而言之:选择排序两层循环,外层循环数组的长度
(i=0,i<len-1),内层循环(j=i+1,j<len)去查找值与记录的最小值比较,如果小于记录值,更新当前最小值的索引,然后,内层循环结束,判断最小值的索引是否与外层的索引不一致,是的话,交换位置
动画模拟

选择排序的实现:
- 定义最小值的索引,
minIndex=0 - 找最小值的索引,最小值小于当前的值,更换索引
- 如果最小值索引不等于当前最外层的索引,说明内层是找到更小的值,两个值位置进行交换
javascript
/**
* 选择排序
* @param arr{Array}
*/
const selectionSort = (arr)=> {
// 定义最小值的索引,minIndex=0
let minIndex = 0
for (let i = 0; i < arr.length - 1; i++) {
minIndex = i
// 找最小值的索引
for (let j = i+1; j < arr.length; j++) {
// 如果记录的最小值小于当前的值,更换索引
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
// 如果最小值索引不等于当前最外层的索引,说明内层是找到更小的值
if (minIndex!==i){
// 两个值进行交换
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
}
return arr
}
console.log(selectionSort([34, 10, 64, 51, 32, 21])); // 输出: [10, 21, 32, 34, 51, 64]
console.log(selectionSort([5, 1, 4, 2, 8])); // 输出: [1, 2, 4, 5, 8]
console.log(selectionSort([])); // 输出: []
console.log(selectionSort([1])); // 输出: [1]
console.log(selectionSort([9, 7, 7, 3, 1, 2, 4])); // 输出: [1, 2, 3, 4, 7, 7, 9]
解释:
- 外层循环:
for (let i = 0; i < arr.length - 1; i++)控制排序的轮次。每次循环确定一个元素的最终位置。 - 内层循环:
for (let j = i+1; j < arr.length; j++)用于在未排序部分中寻找最小值的索引。 - 交换操作:如果找到的最小值索引
minIndex不等于当前轮次的起始位置i,则交换这两个位置的值。
时间复杂度分析:
- 最好情况:即使数组已经是有序的,选择排序仍然会执行所有比较和交换操作,时间复杂度为 O(n^2)。
- 最坏情况:数组完全逆序,时间复杂度为 O(n^2)。
- 平均情况:无论数组的状态如何,选择排序的时间复杂度均为 O(n^2)。
空间复杂度分析:
- 空间复杂度:选择排序是原地排序算法,不需要额外的存储空间,因此空间复杂度为 O(1)。
特点:
- 稳定性:选择排序不是稳定的排序算法。因为在排序过程中,相等的元素可能会改变原来的顺序。
- 适应性:选择排序对小规模数据集或已经部分有序的数据集表现尚可,但对于大规模数据集来说效率较低。
虽然选择排序的时间复杂度较高,但在某些情况下,特别是对于小规模数据集,选择排序仍然是一个简单且容易理解的排序算法。