Python3 选择排序

亦凉 2023-06-12 06:28 6阅读 0赞

参考：《算法图解》第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 一开始就预留座位，位置不够还是要挪  
链表：看电影位置不够分开坐，上一个人记住下一个人的位置（像寻宝游戏），缺点：只能顺序访问