选择排序

7.1 定义选择排序

选择排序 (Selection Sort) —— 这是个排序算法，它会在未排序部分 找到最小的元素并与这部分的第一个元素交换位置。这个过程会重复进行， 直到整个数组排序完成。

工作原理：

1. 从数组的第一个元素开始。
2. 在未排序的部分找到最小的元素。
3. 将最小的元素与未排序部分的第一个元素交换位置。
4. 对下一个元素重复这个过程，直到整个数组排序完成。

逐步过程

1. 找到数组中的最小元素并与第一个元素交换位置。
2. 对剩下的数组（从第二个元素开始）重复这个过程。
3. 持续这个过程，直到整个数组排序完成。

选择排序的时间和空间复杂度

时间复杂度：

• 最坏情况: O(n^2) — 发生在元素按逆序或随机顺序排列时。
• 平均情况: O(n^2) — 发生在元素随机排列时。
• 最好情况: O(n^2) — 即使数组已经排序，算法仍然会进行相同的比较。

空间复杂度：

O(1) — 因为算法只使用常量的额外空间（只是几个用于存储临时值的变量）。

7.2 实现选择排序算法

该算法的实现非常简单：

步骤1：在所有元素中找到最小的元素并与第一个元素交换位置。

步骤2：在所有元素中找到最小的元素（除了第一个）并与第二个元素交换位置。

步骤3：在所有元素中找到最小的元素（除了前两个）并与第三个元素交换位置。

Python实现：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 找到未排序部分的最小元素 min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j
        # 将找到的最小元素与未排序部分的第一个元素交换 arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # 返回排序后的数组

# 示例使用：
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("排序后的数组:", sorted_arr)
# 输出: 排序后的数组: [11, 12, 22, 25, 64]

算法工作示例：

1. 第一次遍历 (i = 0):
   1. 在未排序数组 [64, 25, 12, 22, 11] 中找到最小元素 (11)。
   2. 交换 11 和 64。
   3. 数组: [11, 25, 12, 22, 64]
2. 第二次遍历 (i = 1):
   1. 在未排序数组 [25, 12, 22, 64] 中找到最小元素 (12)。
   2. 交换 12 和 25。
   3. 数组: [11, 12, 25, 22, 64]
3. 第三次遍历 (i = 2):
   1. 在未排序数组 [25, 22, 64] 中找到最小元素 (22)。
   2. 交换 22 和 25。
   3. 数组: [11, 12, 22, 25, 64]
4. 第四次遍历 (i = 3):
   1. 在未排序数组 [25, 64] 中找到最小元素 (25)。
   2. 25 已经在正确位置，不需要交换。
   3. 数组: [11, 12, 22, 25, 64]

算法结束，因为所有元素都已排序。