选择排序(Selection Sort)
【摘要】 选择排序(Selection Sort)
选择排序(Selection Sort)
认识
选择排序基本思想是
- 首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置。
- 接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。
- 以此类推，直到所有元素均排序完毕。
分类：属于选择排序类，是原地排序算法
稳定性：不稳定排序算法（相等元素的相对位置可能改变）
时间复杂度：
- 最坏情况：O(n²)
- 最好情况：O(n²)
- 平均情况：O(n²)
空间复杂度：
O(1)，只需要常数级别的额外空间
特点：
交换次数少，每次只交换一次
比较次数多，无论数组初始状态如何
不适合大规模数据排序
选择排序的原理
选择排序的工作过程可以分为以下步骤：
- 将数组分为已排序区和未排序区，初始时已排序区为空
- 在未排序区中找到最小（或最大）的元素
- 将这个元素与未排序区的第一个元素交换位置
- 将已排序区的范围扩大一个元素
- 重复步骤2-4，直到整个数组排序完成
适用场景
选择排序适用于以下场景：
- 小规模数据排序
- 内存受限的环境（空间复杂度低）
- 对交换操作有较高成本的情况（交换次数少）
- 对算法简单性要求高的情况
选择排序的优缺点
优点：
- 实现简单，容易理解
- 空间复杂度低，只需要O(1)的额外空间
- 交换次数少，每次排序只交换一次
- 不受数据初始顺序影响，时间复杂度始终是O(n²)
缺点：
- 时间复杂度高，不适合大规模数据
- 不稳定排序，相等元素的相对位置可能改变
- 即使数组已经有序，仍然需要进行O(n²)的比较
实现
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>选择排序</title>
</head>
<body>
<script>
// 解法1 选择排序
const optimizedSelectionSort = (arr) => {
const n = arr.length;
// 外层循环控制排序轮数
for(let i=0;i<n-1;i++){
// 假设当前未排序区的第一个元素是最小的
let minIndex = i;
// 内层循环在未排序区找最小元素的索引
for(let j=i+1;j<n;j++){
if(arr[j]<arr[minIndex]){
minIndex=j;
}
}
// 如果找到的最小元素不是当前位置，则交换
if(minIndex!==i){
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
};
// 示例使用
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log("原始数组:", arr);
console.log("排序后数组:", optimizedSelectionSort(arr));
</script>
</body>
</html>
优化-双向选择排序,减少比较次数
// 1 优化 -双向选择排序,减少比较次数
const optimizedSelectionSort = (arr) => {
const n = arr.length;
let left = 0;
let right = n - 1;
while(left < right){
let minIndex = left;
let maxIndex = left;
// 优化内层循环，减少比较次数
for (let i = left + 1; i <= right; i++) {
// 一次比较同时更新最小和最大值
if (arr[i] < arr[minIndex]) {
minIndex = i;
} else if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
// 交换最小值到左端
if (minIndex !== left) {
[arr[left], arr[minIndex]] = [arr[minIndex], arr[left]];
// 如果最大值原本在left位置，已经被交换到minIndex位置
if (maxIndex === left) {
maxIndex = minIndex;
}
}
// 交换最大值到右端
if (maxIndex !== right) {
[arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]];
}
left++;
right--;
return arr;
}
};
添加提前终止条件
在排序的过程之中，有时候我们会遇到后面已经排序的情况，就可以避免重复比对，这个时候可以提前添加终止条件
// 2 添加提前终止条件
function optimizedSelectionSort(arr) {
const n = arr.length;
let left = 0;
let right = n - 1;
while (left < right) {
let minIndex = left;
let maxIndex = left;
let isSorted = true; // 添加标记，假设已排序
for (let i = left + 1; i <= right; i++) {
// 如果发现逆序对，标记为未排序
if (arr[i] < arr[i - 1]) {
isSorted = false;
}
if (arr[i] < arr[minIndex]) {
minIndex = i;
} else if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
// 如果已经有序，提前终止
if (isSorted) {
break;
}
// 交换最小值到左端
if (minIndex !== left) {
[arr[left], arr[minIndex]] = [arr[minIndex], arr[left]];
if (maxIndex === left) {
maxIndex = minIndex;
}
}
// 交换最大值到右端
if (maxIndex !== right) {
[arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]];
}
left++;
right--;
}
return arr;
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）