算法原理
选择排序（Selection Sort）是一种简单的排序算法，它的核心思想是：在每一轮的排序中，从未排序的部分中找到最小（或最大）的元素，并将其放到已排序部分的末尾。
- 初始状态：数组被分为两部分，已排序部分和未排序部分。开始时，已排序部分为空，而未排序部分包含所有元素。
- 第一轮：从未排序部分中找到最小的元素，将其与未排序部分的第一个元素交换位置。这时，已排序部分包含了一个元素，即当前找到的最小元素。
- 第二轮：继续在剩下的未排序部分中找到最小元素，再将其与未排序部分的第一个元素交换。这时，已排序部分包含两个元素，且这两个元素是按顺序排列的。
- 重复上述步骤：不断重复这一过程，直到所有元素都被排序，未排序部分为空。
时间复杂度：选择排序的时间复杂度为 (O(n^2))，其中 (n) 是数组的元素数量。尽管它的效率不高，但由于其简单性和容易理解，选择排序在教学中广泛使用。
选择排序的概念可以追溯到20世纪40年代左右。随着计算机科学的发展，学者们开始研究如何让计算机高效地排列一组数据。虽然没有明确的记录显示选择排序由谁首先提出，但它与早期的排序算法（如冒泡排序）一起，成为了计算机科学的基础算法之一。
在最早的计算机上，存储和计算资源非常有限。算法设计的一个重要目标是尽可能减少交换操作，因为交换通常需要较多的资源。选择排序通过每轮只进行一次交换（在找出最小元素后），在这方面表现得相对高效。
选择排序的故事可以和早期的“打牌”经验联系在一起。想象你在玩纸牌时，需要对手中的牌进行排序。在没有其他人帮助的情况下，你可能会采取选择排序的策略：先找到手中最小的一张牌，把它放在最左边，然后继续在剩下的牌中找到最小的一张，放在左边的第二个位置，依此类推，直到手中的牌全部按从小到大的顺序排列好。
这种策略虽然简单，但也容易理解，特别适合资源有限的情况，如早期的计算机。随着计算机性能的提升和更多复杂算法的出现，选择排序逐渐被更高效的算法（如快速排序、归并排序）所取代，但它作为计算机科学教育中的经典算法，至今仍被广泛教授和使用。
过程分析
假设我们有一个数组 arr，内容为 [64, 25, 12, 22, 11]，我们使用选择排序对其进行升序排列。过程如下：
初始状态：
- 数组：
[64, 25, 12, 22, 11] - 已排序部分：
[] - 未排序部分：
[64, 25, 12, 22, 11]
第一轮：
- 在未排序部分
[64, 25, 12, 22, 11]中找到最小值11，与第一个元素64交换。 - 数组：
[11, 25, 12, 22, 64] - 已排序部分：
[11] - 未排序部分：
[25, 12, 22, 64]
第二轮：
- 在未排序部分
[25, 12, 22, 64]中找到最小值12，与第一个元素25交换。 - 数组：
[11, 12, 25, 22, 64] - 已排序部分：
[11, 12] - 未排序部分：
[25, 22, 64]
第三轮：
- 在未排序部分
[25, 22, 64]中找到最小值22，与第一个元素25交换。 - 数组：
[11, 12, 22, 25, 64] - 已排序部分：
[11, 12, 22] - 未排序部分：
[25, 64]
第四轮：
- 在未排序部分
[25, 64]中找到最小值25，无需交换，因为它已经在正确的位置。 - 数组：
[11, 12, 22, 25, 64] - 已排序部分：
[11, 12, 22, 25] - 未排序部分：
[64]
第五轮：
- 只剩下一个元素
64，它自动排序完成。 - 数组：
[11, 12, 22, 25, 64] - 已排序部分：
[11, 12, 22, 25, 64] - 未排序部分：
[]
最终，数组从 [64, 25, 12, 22, 11] 排列成 [11, 12, 22, 25, 64]，完成了选择排序的过程。
通过这个过程，我们可以清楚地看到每一步如何找到未排序部分的最小值，并将其放到正确的位置上，直到整个数组排序完毕。这种方法尽管简单，但非常直观，并且不需要大量的内存或复杂的操作，特别适合理解基本的排序概念。
动态实现
代码语言：javascript复制<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Selection Sort Visualization</title>
<style>
body {
font-family: 'Arial', sans-serif;
background-color: #f4f4f9;
color: #333;
margin: 0;
padding: 20px;
display: flex;
flex-direction: column;
align-items: center;
justify-content: center;
height: 100vh;
}
h1 {
color: #4CAF50;
font-size: 2.5rem;
margin-bottom: 20px;
}
.container {
display: flex;
justify-content: space-around;
align-items: flex-end;
width: 80%;
max-width: 800px;
background-color: #fff;
padding: 20px;
border-radius: 10px;
box-shadow: 0 4px 8px rgba(0, 0, 0, 0.1);
}
.bar {
width: 30px;
margin-right: 4px;
background-color: #1E90FF;
border-radius: 5px 5px 0 0;
transition: background-color 0.3s, transform 0.3s;
display: flex;
align-items: flex-end;
justify-content: center;
font-size: 0.8rem;
color: white;
padding-bottom: 5px;
}
.bar:hover {
background-color: #4682B4;
transform: scale(1.05);
}
button {
margin-top: 20px;
padding: 10px 20px;
font-size: 1rem;
background-color: #4CAF50;
color: white;
border: none;
border-radius: 5px;
cursor: pointer;
transition: background-color 0.3s;
}
button:hover {
background-color: #45a049;
}
</style>
</head>
<body>
<h1>Selection Sort Visualization</h1>
<div id="array" class="container"></div>
<button onclick="selectionSort()">Start Sorting</button>
<script>
const array = [64, 25, 12, 22, 11];
const container = document.getElementById('array');
function renderArray(arr) {
container.innerHTML = '';
arr.forEach(value => {
const bar = document.createElement('div');
bar.classList.add('bar');
bar.style.height = `${value * 3}px`;
bar.textContent = value;
container.appendChild(bar);
});
}
async function selectionSort() {
const arr = [...array];
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]];
renderArray(arr);
await new Promise(resolve => setTimeout(resolve, 500)); // 等待 0.5 秒
}
}
}
renderArray(array);
</script>
</body>
</html>
下面是对 selectionSort 函数中代码的详细解释：
async function selectionSort() {
const arr = [...array]; // 创建数组的副本，避免直接修改原数组
const n = arr.length; // 获取数组的长度
for (let i = 0; i < n - 1; i ) { // 外层循环，控制选择排序的轮次
let minIndex = i; // 假设当前第 i 个元素是最小值，并将其索引存储在 minIndex 中
for (let j = i 1; j < n; j ) { // 内层循环，遍历 i 后面的元素
if (arr[j] < arr[minIndex]) { // 如果找到比当前最小值还小的元素
minIndex = j; // 更新最小值的索引
}
}
if (minIndex !== i) { // 如果找到的最小值索引不是当前索引
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 交换当前元素与找到的最小值
renderArray(arr); // 更新数组的可视化表示
await new Promise(resolve => setTimeout(resolve, 500)); // 等待 0.5 秒，用于展示排序过程中的变化
}
}
}代码解释
const arr = ...array;这里使用了 ...array 进行数组的浅拷贝。这样做的目的是创建一个 array 数组的副本，以防止原始数组在排序过程中被修改。这是为了确保原始数据的安全，同时能够自由操作副本进行排序。
const n = arr.length;这行代码获取数组的长度 n，后续将使用这个值来控制循环次数。
外层循环 for (let i = 0; i < n - 1; i ) {}这个循环控制了选择排序的轮次。每轮循环的目标是将数组的第 i 个元素设置为当前未排序部分的最小值。
let minIndex = i;假设当前第 i 个元素是未排序部分的最小值，并将 minIndex 变量设为当前索引 i。
内层循环 for (let j = i 1; j < n; j ) {}这个循环从 i 1 开始遍历数组的剩余部分，用于寻找是否存在比 arri 更小的元素。如果找到更小的元素，则更新 minIndex 的值。
if (arrj < arrminIndex) { minIndex = j; }通过比较 arrj 和 arrminIndex，确定更小的元素。如果找到比当前最小值还小的元素，则更新 minIndex 的索引。
if (minIndex !== i) { [arri, arrminIndex] = [arrminIndex, arri]; }如果 minIndex 不等于 i，说明在剩余部分找到更小的元素，需要将其与当前元素 arri 进行交换。使用数组解构交换两个元素的位置。
renderArray(arr);调用 renderArray 函数，重新渲染数组的可视化表示，让用户看到当前数组的变化。
await new Promise(resolve => setTimeout(resolve, 500));这里使用了 await 和 Promise 的组合，延迟 0.5 秒后继续执行。这是为了让用户能清楚地看到每一步的排序过程。如果没有这个延迟，排序会瞬间完成，无法可视化。
总结
整个代码实现了选择排序算法的基本逻辑，并通过逐步更新数组的可视化表示，帮助用户理解排序过程。外层循环确保每次选择一个最小值放在正确位置，而内层循环在剩余未排序的部分中寻找最小值。通过异步延迟，用户可以逐步看到排序的每一步。
