本章内容
- 学习两种最基本的数据结构:数组、链表
- 学习第一种排序算法:选择排序
数组和链表
- 需要存储多项数据时,有两种基本方式——数组和链表。
- 在数组中所有的数据在内存中都是相连的,如要添加新元素时,原本数据后没有空余空间时,计算机就会迁移这些数据到合适的内存空间。
- 额外请求的位置可能根本用不上,这将浪费内存,即使没有使用,其他数据也利用不了。
- 数据存储超过预先分配的空间后会被整体迁移。
链表
- 链表中的元素可能会被存储在任何地方。
- 链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。
- 在链表中添加元素很容易:只需要将其放入内存,并将其地址存储到前一个元素中。
- 链表支持顺序访问。
数组
- 链表中存在着这样的问题,在需要读取链表的最后一个元素时,并不能直接读取,因为不知道它所处的地址,必须先访问元素#1,从中获取元素#2的地址,再访问元素#2并从中获取元素#3的地址,…,直到访问到最后一个元素。如果需要跳跃访问,链表的效率真的很低。
- 数组不一样,我们知道每个元素的
地址索引。 - 数组支持随机访问。
常见的数组和链表操作的运行时间:
数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n)
O(1)
O(n)=线性时间
O(1)=常量时间
选择排序
- 运行时间:O(n^2)
示例代码:
- 找出数组中最小元素:
def findSmallest(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
2.编写排序算法
def selectionSort(arr):
newArry = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArry.append(arr.pop(smallest)) #arr剔除一个值,newArry添加一个
return newArry
- 完整运行:
def findSmallest(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):
newArry = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArry.append(arr.pop(smallest))
return newArry
print(selectionSort([5, 3, 6, 9, 9, 6, 9]))
小结
- 计算机内存犹如一大堆抽屉
- 需要存储多个元素时,可使用数组或链表
- 数组的元素都在一起
- 链表的元素是分开的,其中每个元素存储了下一个元素的地址
- 数组的读取速度很快
- 链表的插入和删除速度很快
- 在同一个数组中,所有元素的类型都必须相同(都为int,double等)
发表回复