Python算法——选择排序

选择排序（Selection Sort）是一种简单的排序算法，它的基本思想是在未排序的部分中选择最小（或最大）的元素，然后将其放在已排序部分的末尾。选择排序不同于冒泡排序，它不需要反复交换元素，因此在某些情况下可能比冒泡排序更快。本文将详细介绍选择排序的工作原理和Python实现。

选择排序的工作原理

选择排序的基本思想是：

1. 从未排序的数组中找到最小的元素。
2. 将最小元素与未排序部分的第一个元素交换位置。
3. 重复上述两步，不断扩大已排序部分，缩小未排序部分，直到整个数组有序。

选择排序的核心思想是每一轮选择一个最小的元素，并将它交换到已排序部分的末尾。这一过程持续多轮，每轮选择一个最小的元素，直到整个数组有序。

下面是一个示例，演示选择排序的过程。我们以升序排序为例：

原始数组：[64, 25, 12, 22, 11]

1. 第一轮选择，最小元素为 11，交换位置后数组变为：[11, 25, 12, 22, 64]
2. 第二轮选择，最小元素为 12，交换位置后数组变为：[11, 12, 25, 22, 64]
3. 第三轮选择，最小元素为 22，交换位置后数组变为：[11, 12, 22, 25, 64]
4. 第四轮选择，最小元素为 25，交换位置后数组变为：[11, 12, 22, 25, 64]
5. 第五轮选择，最小元素为 64，交换位置后数组不变：[11, 12, 22, 25, 64]

Python实现选择排序

下面是Python中的选择排序实现：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        arr[i], arr[min_index] = arr[min_index], arr[i]

• arr 是待排序的数组。
• n 表示数组的长度。
• 外层循环 for i in range(n) 用于控制遍历的轮数。
• 内层循环 for j in range(i+1, n) 用于查找未排序部分中的最小元素。
• min_index 用于记录最小元素的索引，如果找到更小的元素，更新 min_index。
• 在内层循循环结束后，将最小元素与当前轮次的第一个元素交换位置。

示例代码

下面是一个使用Python进行选择排序的示例代码：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        arr[i], arr[min_index] = arr[min_index], arr[i]

# 测试排序
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的数组:", arr)

时间复杂度

选择排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。与冒泡排序一样，选择排序不是最高效的排序算法，但它是一种简单易懂的算法，适用于小型数据集。

总之，选择排序是一种简单的排序算法，通过选择最小元素并将其放在已排序部分的末尾，实现了排序数组的目标。了解选择排序有助于理解排序算法的基本原理，并为学习更高效的排序算法奠定了基础。