python 选择排序（Selection Sort）

选择排序（Selection Sort）

选择排序是一种简单的排序算法。它的基本思想是：每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。重复这个过程，直到所有元素都被排序。

选择排序的步骤：

1. 找到最小元素：在未排序部分中找到最小的元素。
2. 交换位置：将最小元素与未排序部分的第一个元素交换位置。
3. 重复过程：重复上述步骤，直到所有元素都被排序。

时间复杂度：

• 最坏情况：O(n²)
• 最好情况：O(n²)
• 平均情况：O(n²)

选择排序的时间复杂度始终是 O(n²)，因为它每次都需要遍历未排序部分来找到最小元素。

空间复杂度：

• O(1) —— 选择排序是一种原地排序算法，不需要额外的存储空间。

Python 实现

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 假设当前索引 i 的元素是最小的
        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]

选择排序的详细过程

以数组 [64, 25, 12, 22, 11] 为例：

1. 第一轮：

   • 找到最小元素 11，与第一个元素 64 交换。
   • 数组变为 [11, 25, 12, 22, 64]。

2. 第二轮：

   • 在未排序部分 [25, 12, 22, 64] 中找到最小元素 12，与第二个元素 25 交换。
   • 数组变为 [11, 12, 25, 22, 64]。

3. 第三轮：

   • 在未排序部分 [25, 22, 64] 中找到最小元素 22，与第三个元素 25 交换。
   • 数组变为 [11, 12, 22, 25, 64]。

4. 第四轮：

   • 在未排序部分 [25, 64] 中找到最小元素 25，与第四个元素 25 交换（无需交换）。
   • 数组保持不变 [11, 12, 22, 25, 64]。

5. 第五轮：

   • 最后一个元素 64 已经位于正确位置。
   • 排序完成。

选择排序的优缺点

优点：

• 实现简单，易于理解。
• 对于小规模数据排序效果较好。
• 交换次数较少，最多交换 n-1 次。

缺点：

• 时间复杂度较高，不适合处理大规模数据。
• 无论输入数据是否有序，时间复杂度始终为 O(n²)。

选择排序虽然简单，但在实际应用中由于其较高的时间复杂度，通常不用于处理大规模数据。