1.瓦特 is 选择排序?
选择排序（Selection sort）是一种简单直观的[排序算法]。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
图片来自维基百科图片来自维基百科
2. Talk is cheap, show me the code
- 下面写法是将一个无序的数组搬进另一个空数组中
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))
运行结果
- 本数组倒腾的元素的
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
