用Python实现选择排序算法

2023-04-16 00:00:00 选择 算法 排序

选择排序算法是一种简单直观的排序算法，在实现上利用了数组下标的特性。其基本思想是每次选出当前最小或最大的元素，放到已排序区间的末尾。具体实现分为两个步骤：

  1. 遍历待排序区间，找到最小（或最大）元素的下标；
  2. 将最小（或最大）元素与待排序区间的第一个元素交换位置。

以下是用Python实现选择排序算法的代码：

def selection_sort(arr):
    """选择排序算法"""
    n = len(arr)
    for i in range(n-1):
        # 查找最小元素的下标
        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 = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(selection_sort(arr))  # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

# 字符串作为范例
arr = ['pidancode.com', '皮蛋编程', 'hello', 'world']
print(selection_sort(arr))  # ['hello', 'pidancode.com', '皮蛋编程', 'world']

在上面的代码中，我们先定义了一个selection_sort函数，接收一个待排序的列表为输入，返回一个已排序的列表。在函数内部，我们使用两个for循环实现选择排序的两个步骤。具体来说：

  • 外层循环i遍历待排序区间的最后一个元素位置n-2，因为最后一个元素在内层循环过程中已经排序完毕；
  • 内层循环j从i+1开始遍历待排序区间，找到最小元素的下标min_index；
  • 如果找到了更小的元素，就将min_index更新为j；
  • 内层循环结束后，如果min_index不等于i，说明找到了更小的元素，则将arr[i]和arr[min_index]交换位置。

最后，我们调用selection_sort函数对一个整型列表和一个字符串列表进行测试，结果都是正确的。

相关文章