Python3 选择排序

参考：《算法图解》第2章 选择排序 

$ 选择排序 每次从数组中找到最小值(或最大值)，从旧数组中剔除，并append到新的数组 【例】你用音乐APP听歌，对于每个歌手记录了TA的曲目播放次数，现在要将这个列表从打到小排序，从而某种程度上将你喜欢的歌手排序 遍历这个列表，找到作品播放次数最多的歌手，并将TA添加到一个新列表，列表2 第二轮遍历列表(已去除排行第一的歌手)找到作品播放次数最多的歌手，并将TA添加到列表2 ……不断从列表中找出当前最大值，直到列表只剩一个元素

需要比较的次数 (n-1) + (n-2) +...+ 1 = [(n-1) + 1]*(n-1)/2 时间复杂度 O(n x n)

$ 选择排序代码实现

#寻找数组中的最小值 def findSamallest(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(arr): newArr = [] for i in range(len(arr)): smallest = findSamallest(arr) newArr.append(arr.pop(smallest)) return newArr print(selectionSort([5,3,6,2,10]))

arr=[5,3,6,2,10]  , newArr=[] arr=[5,3,6,10]  , newArr=[2] arr=[5,6,10]  , newArr=[2,3] arr=[6,10]  , newArr=[2,3,5] arr=[10]  , newArr=[2,3,5,6] arr=[]  , newArr=[2,3,5,6,10]

$ 数组和链表 数组：看电影坐在一起，位置不够挪地方 or 一开始就预留座位，位置不够还是要挪 链表：看电影位置不够分开坐，上一个人记住下一个人的位置（像寻宝游戏），缺点：只能顺序访问

 数组链表读取O(1)O(n)插入O(n)O(1)删除O(n)O(1)