[数据结构与算法]《算法图解》学习笔记-选择排序

Python实现选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

代码

# 选择排序:将数组中元素按从小到大的顺序排列
# 先编写一个用于找出数组中最小元素的函数

def findSmall(arr):
    smallest = arr[0]  # 存储最小的值
    smallest_index = 0  # 存储最小元素的索引
    for i in range(1, len(arr)):  # 索引从1开始,因为索引为0的值已经被赋予最小的值
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index


# 排序算法  对数组进行排序
def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmall(arr)
        newArr.append(arr.pop(smallest))  # pop为取数组的最后一个元素,即-1
    return newArr


# 主函数
print(selectionSort([5, 3, 9, 19, 34]))

运行结果