选择排序（Selection Sort）

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理如下：

1. 遍历数组：从待排序的数列中，找到当前未排序部分（即整个数组或已排序部分之后的部分）中的最小（或最大，取决于排序方式）元素。

2. 交换位置：将找到的最小元素与未排序部分的第一个元素交换位置，这样最小元素就被放到了正确的位置。

3. 重复以上过程：接着对剩余未排序部分（即除了已排好序的首个元素外的部分）再次进行上述操作。每次遍历都会将当前未排序部分的最小元素放到正确的位置。

4. 遍历完整个数组：持续进行上述两步操作，每次都会将当前未排序部分的最小元素放到已排序部分的末尾。随着遍历次数的增加，已排序部分逐渐增大，直至整个数组排序完成。

时间复杂度：

• 最好情况（输入数组已经是有序的）：尽管数组已经有序，选择排序仍需进行 n-1 轮遍历和 n-1 次交换，时间复杂度为 O(n2)。
• 最坏情况（输入数组逆序排列）：同样需要进行 n-1 轮遍历和 n-1 次交换，时间复杂度为 O(n2)。
• 平均情况：时间复杂度也为 O(n2)。

空间复杂度：选择排序是原地排序算法，只需要常数级别的额外空间用于临时存储交换的元