基本思想
- 从小到大依次选出第 1 小的元素、第 2 小的元素、…；
- 通过交换达到 选择 和 排序 的目的；
- 循环不变的性质（循环不变量）：区间
nums[0, i)里保存了数组里最小的 i 个元素，并且按照升序排序；
图解
具体步骤
每一轮都选取 未排定的部分 的最小元素，然后将它 交换 到 未排定的部分 的第 1 个位置；
例：将数组
[8, 3, 9, 6, 4, 1, 5, 2, 10, 7]升序排序；
- 首先经过一次扫描，通过逐个比较，找到整个数组中最小的元素 1 ，把它交换到这个数组的开头，交换以后，1 就呆在了最终应该在的位置；
- 接下来，继续扫描未排定的部分，选出最小的元素 2 ，把它交换到未排定的部分的第 1 个位置，这个位置就是 2 这个元素最终应该呆的位置；
- 接下来的操作，就不赘述了，直到 未排定的部分 只剩下一个元素，此时就不用比较了，它一定是整个数组中最大的那个元素；
- 到此为止，就得到了原始数组的升序排序结果；
特点
交换的次数最少：如果一个排序任务交换的成本很高，可以考虑使用选择排序；
运行时间与输入无关：
- 每一趟扫描，除了扫描的元素比上一轮少了一个以外，选择排序没有记住更多的信息；一个极端的例子是，已经是排好序的数组，选择排序还需要一次又一次地扫描；
- 这两点是选择排序区别于其它排序算法的特点。后续学到的算法或多或少都与输入数据的形态相关，即一个已经排好序的数组或者一个接近排好序的数组和一个随机数组，使用其它的排序算法它们所消耗的时间是有差别的；
复杂度
-
时间复杂度：
O(N^2)- n 表示数组的长度
- 循环次数
第 i 轮 比较次数 第 1 轮 与 N−1 个数比较 第 2 轮 与 N−2 个数比较 第 3 轮 与 N−3 个数比较 … … 第 N-1 轮 与 1 个数比较 (N−1) + (N−2) + (N−3) + ... + 1 = (N - 1 + 1)(N - 1)/2 = N(N - 1)/2，则时间复杂度为O(N^2)；
-
空间复杂度：
O(1)
代码实现
function selectSort(nums) {
let len = nums.length;
// 最后一轮只有一个元素，一定是最大的元素，因此写 i < len - 1
for (let i = 0; i < len - 1; i++) {
// 在 [i + 1, len - 1] 区间里选择最小的元素的下标
// 这种一趟扫描选出最值的方法，有一个很形象的名字叫：打擂台算法
let minIndex = i;
for (let j = i + 1; j < len; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
// 将最小的元素交换到未排序的第一项
[nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
}
return nums;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
比较排序🔮 冒泡排序
上一篇
评论
