博客

详解选择排序算法原理与使用方法

当我们需要对一组数据进行排序时，常常会用到选择排序算法。

选择排序算法简介

选择排序算法（Selection Sort）是一种简单直观的排序算法，其基本思想是首先找到最小值（或最大值），然后将其移动到排序的起始位置，再继续在剩余的数组元素中查找最小值，直至整个数组有序。

实现步骤

  1. 首先设置minIndex为当前未排序部分的第一个元素下标，即minIndex=0。
  2. 从未排序部分中遍历，查找未排序部分最小元素的下标，即找到当前范围内的最小值minIndex。
  3. 将当前范围内的第一个元素与找到的最小值进行交换。
  4. 范围缩小至未排序部分的下一个元素，返回到步骤2。

代码实现

下面是选择排序的 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)

示例说明

示例一

假设有一组整数数组 [64, 25, 12, 22, 11] ，需要使用选择排序算法将其从小到大排序。

首先，min_index 被设置为未排序部分的第一个元素 64 的下标 0。

在第一次遍历中，我们需要在未排序的元素中找到最小值。我们从 i+1=1 开始遍历，直到 n=5：

  • 当 j=1 时，arr[j]=25，比 arr[min_index]=64 小，因此更新最小值的位置，min_index=1。
  • 当 j=2 时，arr[j]=12，比 arr[min_index]=25 小，因此更新最小值的位置，min_index=2。
  • 当 j=3 时，arr[j]=22，比 arr[min_index]=12 大，不需要更新。
  • 当 j=4 时，arr[j]=11，比 arr[min_index]=12 小，因此更新最小值的位置，min_index=4。

最后，在未排序部分 25、12、22 和 11 中，我们找到了最小值 11。我们将其移动到未排序部分的起始位置，即与 arr[i]=64 进行交换，得到数组 [11, 25, 12, 22, 64]。

然后，i=1，未排序部分为 [25, 12, 22, 64]，min_index 被设置为 1。

在第二次遍历中，我们需要在未排序的元素中找到最小值。我们从 i+1=2 开始遍历，直到 n=5：

  • 当 j=2 时，arr[j]=12，比 arr[min_index]=25 小，因此更新最小值的位置，min_index=2。
  • 当 j=3 时，arr[j]=22，比 arr[min_index]=12 大，不需要更新。
  • 当 j=4 时，arr[j]=64，比 arr[min_index]=12 大，不需要更新。

最后，在未排序部分 25、22 和 64 中，我们找到了最小值 22。我们将其移动到未排序部分的起始位置，即与 arr[i]=25 进行交换，得到数组 [11, 22, 12, 25, 64]。

然后，i=2，未排序部分为 [12, 25, 64]，min_index 被设置为 2。

在第三次遍历中，我们需要在未排序的元素中找到最小值。我们从 i+1=3 开始遍历，直到 n=5：

  • 当 j=3 时，arr[j]=25，比 arr[min_index]=64 小，不需要更新。
  • 当 j=4 时，arr[j]=64，比 arr[min_index]=25 大，不需要更新。

最后，在未排序部分 12 和 25 中，我们找到了最小值 12。我们将其移动到未排序部分的起始位置，即与 arr[i]=12 进行交换，得到数组 [11, 22, 12, 25, 64]。

然后，i=3，未排序部分为 [25, 64]，min_index 被设置为 3。

在第四次遍历中，我们需要在未排序的元素中找到最小值。我们从 i+1=4 开始遍历，直到 n=5：

  • 当 j=4 时，arr[j]=64，比 arr[min_index]=25 大，不需要更新。

最后，在未排序部分 25 中，我们找到了最小值 25。我们将其移动到未排序部分的起始位置，即与 arr[i]=25 进行交换，得到数组 [11, 22, 12, 25, 64]。

最后，我们完成了整个排序过程，最终得到了从小到大排好序的整数数组 [11, 12, 22, 25, 64]。

示例二

下面给出另一个使用选择排序算法的实例，该实例是对字符列表（包括重复字符）进行排序。

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # min_index 存储未排序部分的第一个元素下标
        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]
    return arr

# 测试
arr = ['B', 'D', 'A', 'C', 'D', 'A', 'B']
result = selection_sort(arr)
print("排序后的列表:", result)

在此示例中，我们使用字符列表 [‘B’, ‘D’, ‘A’, ‘C’, ‘D’, ‘A’, ‘B’]，希望将其以字母表顺序从 A 到 Z 排序。对于此示例，排序算法遵循相同的选择排序原则，只是它比第一个示例更容易理解。执行结果为 [‘A’, ‘A’, ‘B’, ‘B’, ‘C’, ‘D’, ‘D’]。

总结

选择排序是一种简单且通用的排序算法。它不需要额外的存储空间，相对容易实现，因此是实现其他复杂算法的基础。然而，它的时间复杂度为 O(n²)，因此在面对较大的数据集时，执行效率可能不够高。

Tags: