选择排序是一种简单直观的比较排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
选择排序的基本思想
选择排序的基本思想是通过多次比较和交换来实现排序。具体步骤如下：
- 从数组的起始位置开始，将当前索引位置作为最小值索引。
- 将该索引位置与后续所有位置进行比较，找出最小值的位置。
- 如果找到的最小值索引不是当前索引，则将它们交换。
- 移动到下一个位置，重复上述步骤，直到排序完成。
选择排序的实现
代码实现
// www.javascriptcn.com code example
function selectionSort(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 numbers = [64, 34, 25, 12, 22, 11, 90];
console.log("排序前:", numbers);
const sortedNumbers = selectionSort(numbers);
console.log("排序后:", sortedNumbers);代码解释
selectionSort函数接受一个数组arr作为参数。- 外层循环变量
i控制排序的轮数，总共进行n-1轮。 minIndex变量用于记录当前遍历过程中的最小值索引。- 内层循环用于遍历数组中剩余未排序的部分，寻找最小值。
- 如果在内层循环中找到了更小的值，更新
minIndex。 - 最后，如果最小值索引与当前索引不同，则交换这两个位置的元素。
选择排序的性能分析
选择排序的时间复杂度为 O(n^2)，无论输入数据如何，它都需要进行固定次数的比较和交换操作。因此，它不适合处理大量数据。
- 最优情况：O(n^2)
- 最坏情况：O(n^2)
- 平均情况：O(n^2)
选择排序的空间复杂度为 O(1)，因为它只需要常数级别的额外空间。
选择排序的应用场景
尽管选择排序的效率不高，但它仍然有一些应用场景，例如：
- 当内存空间非常有限时，选择排序因其原地排序特性而适用。
- 当数据集较小，且对算法复杂度要求不严格时。
- 教学用途，帮助理解基本的排序算法。
总结
选择排序是一种基础的排序算法，虽然它的效率较低，但其简单性和易理解性使其成为学习排序算法的良好起点。希望本章的内容能够帮助您深入理解选择排序的工作原理及其实现方式。