选择排序
选择排序是一种简单直观的排序算法。它的工作原理是：每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。重复这个过程，直到所有元素都排好序。
算法原理
选择排序的基本思想是：将数组分为已排序和未排序两部分。初始时，已排序部分为空，未排序部分包含所有元素。每次从未排序部分选择最小元素，将其与未排序部分的第一个元素交换，然后扩展已排序部分。重复这个过程，直到所有元素都排好序。
算法步骤
- 将数组分为已排序部分（初始为空）和未排序部分（包含所有元素）
- 在未排序部分中找到最小元素
- 将最小元素与未排序部分的第一个元素交换
- 扩展已排序部分，缩小未排序部分
- 重复上述步骤，直到未排序部分为空
时间复杂度
- 最坏情况：O(n²) - 无论数据如何，都需要进行 n(n-1)/2 次比较
- 平均情况：O(n²)
- 最好情况：O(n²) - 即使数据已经有序，仍需进行完整的比较
空间复杂度
O(1) - 选择排序是原地排序算法，只需要常数级别的额外空间。
稳定性
选择排序是不稳定的排序算法。当存在相等元素时，它们的相对顺序可能会改变。
适用场景
- 数据规模较小的排序任务
- 对交换次数敏感的场景（交换次数最多 n-1 次）
- 内存受限的环境（原地排序，空间复杂度低）
优缺点
- 优点：算法简单，易于理解和实现；交换次数少
- 缺点：时间复杂度高，不适合大规模数据；不稳定