python笔试面试项目实战2020百练2选择排序冒泡排序

链表与数组

链表的优势在插入元素方面,需要随机地读取元素时,数组的效率很高,因为可迅速找到数组的任何元素。在链表中,元素并非靠在一起的,你无法迅速计算出第五个元素的内存地址,而必须先访问第一个元素以获取第二个元素的地址,再访问第二个元素以获取第三个元素的地址,以此类推,直到访问第五个元素。

image.png

参考资料

• 本文最新版本地址
• 本文涉及的python测试开发库 谢谢点赞！
• 本文相关海量书籍下载
• 源码地址 https://github.com/china-testing/python-testing-examples interview/ bubble_sort1.py bubble_sort2.py bubble_sort3.py select_sort1.py

练习: 用python列表实现选择排序

你的计算机存储了很多乐曲。对于每个乐队,你都记录了其作品被
播放的次数。

你要将这个列表按播放次数从多到少的顺序排列,从而将你喜欢的乐队排序。该如何做呢?

一种办法是遍历这个列表,找出作品播放次数最多的乐队,并将该乐队添加到一个新列表中。

image.png

再次这样做,找出播放次数第二多的乐队。

image.png

继续这样做,你将得到一个有序列表。

image.png

需要的总时间为 O (n × n )

• 参考答案

image.png

冒泡排序

冒泡排序 多次遍历列表。它⽐较相邻的元素，将不合顺序的交换。每⼀轮遍历都将下⼀个最⼤值放到正确的位置上。本质上，每个元素通过“冒泡”找到⾃⼰所属的位置。

下图展⽰了冒泡排序的第⼀轮遍历过程。深⾊的是正在⽐较的元素。如果列表中有 个元素，那么第⼀轮遍历要⽐较 对。注意，最⼤的元素会⼀直往前挪，直到遍历过程结束。

图片.png

def bubble_sort(items):
    change = True
    num = len(items) -1 
    while change and num > 0:
        change = False
        for i in range(num):
            if items[i] > items[i+1]:
                change = True
                items[i], items[i+1] = items[i+1], items[i]
        num -= 1
        
l = [20,30,40,90,50,60,70,80,100,110]
bubble_sort(l)
print(l)

选择排序

在冒泡排序的基础上做了改进，每次遍历列表时只做⼀次交换。要实现这⼀点，选择排序在每次遍历时寻找最⼤值，并在遍历完之后将它放到正确位置上。和冒泡排序⼀样，第⼀次遍历后，最⼤的元素就位；第⼆次遍历后，第⼆⼤的元素就位，依此类推。若给n个元素排序，需要遍历n-1轮，这是因为最后⼀个元素要到n-1轮遍历后才就位。

下图展⽰了完整的选择排序过程。每⼀轮遍历都选择待排序元素中最⼤的元素，并将其放到正确位置上。

图片.png

'''选择排序经典python面试题'''
def selection_sort(items):
    n = len(items)-1
    for slot in range(n):
        big = last = n - slot
        for location in range(n-slot):
            if items[location] > items[big]:
                big = location
        print(big)
        items[last], items[big] = items[big], items[last]
        
if __name__ == '__main__':        
    l = [20,30,40,90,50,60,70,80,100,110]
    selection_sort(l)
    print(l) # [20, 30, 40, 50, 60, 70, 80, 90, 100, 110]