选择排序（Selection sort）

1.瓦特 is 选择排序?

选择排序（Selection sort）是一种简单直观的[排序算法]。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

图片来自维基百科 图片来自维基百科

2. Talk is cheap, show me the code

1. 下面写法是将一个无序的数组搬进另一个空数组中

def findSmallest(arr): # 查找数组中最小的元素，并返回该下标
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selectionSort(array):
    newArr = [] #这里声明一个新的数组，也可以不声明,下面将介绍另一种方式
    for i in range(len(array)):
        smallet_index = findSmallest(array)
        newArr.append(array.pop(smallet_index)) #将当前的最小元素放入新数组中，并删除旧数组中的该元素
    return newArr

#test
array = [1,4,6,2,7,1,2,4,6,7,7,0]
print(selectionSort(array))

运行结果

2. 本数组倒腾的元素的

def selectionSort2(array):
    for i in range(len(array)):
        smallest_index = i  # 假设一个最元素的下标
        for j in range(i+1, len(array)):
            if array[j] < array[smallest_index]: # 如果发现有比array[smallest_index] 还小的元素，更新smallest_index
                smallest_index = j
        if(i == smallest_index):
            pass
        else:
            array[i], array[smallest_index] = array[smallest_index], array[i] # 交换位置
    return array

array = [1,4,6,2,7,1,2,4,6,7,7,0]
print(selectionSort2(array))

3. 写在最后

image.png

所以大兄弟，动手敲一敲不会有错的！！！