跳到主要内容

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。这个过程会重复进行，直到所有元素都被排序。

选择排序的工作原理​

选择排序的核心思想是“选择”。具体步骤如下：

  1. 找到最小元素：从数组的未排序部分中找到最小的元素。
  2. 交换位置：将找到的最小元素与未排序部分的第一个元素交换位置。
  3. 重复过程：重复上述步骤，直到整个数组排序完成。

示例​

假设我们有一个数组 [64, 25, 12, 22, 11]，我们来看看选择排序是如何工作的。

第一轮​

  • 未排序部分：[64, 25, 12, 22, 11]
  • 最小元素：11
  • 交换 64 和 11，数组变为 [11, 25, 12, 22, 64]

第二轮​

  • 未排序部分：[25, 12, 22, 64]
  • 最小元素：12
  • 交换 25 和 12，数组变为 [11, 12, 25, 22, 64]

第三轮​

  • 未排序部分：[25, 22, 64]
  • 最小元素：22
  • 交换 25 和 22，数组变为 [11, 12, 22, 25, 64]

第四轮​

  • 未排序部分：[25, 64]
  • 最小元素：25
  • 无需交换，数组保持不变 [11, 12, 22, 25, 64]

第五轮​

  • 未排序部分：[64]
  • 最小元素：64
  • 无需交换，数组保持不变 [11, 12, 22, 25, 64]

最终，数组已经排序完成。

选择排序的代码实现​

以下是选择排序的 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]

选择排序的时间复杂度​

选择排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。这是因为每次选择最小元素都需要遍历未排序部分，而这个过程需要重复 n 次。

备注

尽管选择排序的时间复杂度较高，但由于其实现简单，它在某些特定场景下仍然有用。

选择排序的实际应用​

选择排序虽然效率不高，但在某些情况下仍然有其应用价值。例如：

  • 小规模数据排序：当数据量较小时，选择排序的简单实现可能比其他复杂算法更高效。
  • 内存受限的环境：选择排序是一种原地排序算法，不需要额外的存储空间，因此在内存受限的环境中可能是一个不错的选择。

总结​

选择排序是一种简单但效率较低的排序算法。它的核心思想是每次从未排序部分中选择最小元素，并将其放到已排序部分的末尾。尽管它的时间复杂度为 O(n^2)，但在某些特定场景下仍然有其应用价值。

附加资源与练习​

  • 练习：尝试用你熟悉的编程语言实现选择排序，并测试其性能。
  • 进一步学习：了解其他排序算法，如冒泡排序、插入排序和快速排序，比较它们的优缺点。
提示

如果你对排序算法感兴趣，可以尝试实现其他排序算法，并比较它们在不同数据集上的表现。