链表与数组

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

image.png

demo.png

参考资料

• 本文最新版本地址
• 本文涉及的python测试开发库 谢谢点赞！
• 本文相关海量书籍下载
• python工具书籍下载-持续更新
• 本文配套视频在线播放 下载

练习: 用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

def selection_sort(items):    for slot in range(len(items)-1,0, -1):        max = 0        for location in range(1,slot+1):            if items[location] > items[max]:                max = location                items[slot], items[max] = items[max], items[slot]l = [20,30,40,90,50,60,70,80,100,110]bubble_sort(l)print(l)

原著是一个有趣的人,若有侵权,请通知删除