本章内容

• 学习两种最基本的数据结构：数组、链表
• 学习第一种排序算法：选择排序

数组和链表

• 需要存储多项数据时，有两种基本方式——数组和链表。
• 在数组中所有的数据在内存中都是相连的，如要添加新元素时，原本数据后没有空余空间时，计算机就会迁移这些数据到合适的内存空间。
  • 额外请求的位置可能根本用不上，这将浪费内存，即使没有使用，其他数据也利用不了。
  • 数据存储超过预先分配的空间后会被整体迁移。

链表

• 链表中的元素可能会被存储在任何地方。
• 链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
• 在链表中添加元素很容易：只需要将其放入内存，并将其地址存储到前一个元素中。
• 链表支持顺序访问。

数组

• 链表中存在着这样的问题，在需要读取链表的最后一个元素时，并不能直接读取，因为不知道它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2并从中获取元素#3的地址，…，直到访问到最后一个元素。如果需要跳跃访问，链表的效率真的很低。
• 数组不一样，我们知道每个元素的地址索引。
• 数组支持随机访问。

常见的数组和链表操作的运行时间：

数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n)
O(1)

O(n)=线性时间

O(1)=常量时间

选择排序

• 运行时间：O(n^2)

示例代码：

1. 找出数组中最小元素：

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

3. 完整运行：

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等)