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