0. 摘要

• 数据结构之数组和链表
• 排序算法

1.0 内存的工作原理

内存.png

每个抽屉可以看作是一个内存单元。

内存可以看作是寄存处的柜子，每个抽屉都有一个编号。

需要将数据存储到内存是，我们请求计算机为我们提供存储空间，计算机则返回一个存储地址。

那么存储多项数据时，有2种基本方式-----数组和链表。

2.0 数组 & 链表

2.1 数组

• 使用数组意味着所有事项在内存中是相连的。

• 吃午饭
• 喝茶
• 学习

image.png

假如又加入新的事项，只能换到更大的空间上。

为了解决这个问题，有2个办法，

1. 预留位置，即使当前只有3个待办事项，也请计算机预留10个位置。
2. 使用链表。

2.2 链表

• 链表中的元素可存储在内存的任何地方。

  
  image.png

2.3 对比

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

3.0 选择排序

比如，我的歌单里，有我喜欢的歌，以及每首歌的播放次数。

按照播放次数从多到少的顺序，排列初我喜欢的音乐名单。

• 爱我别走 5
• 思念是一种病 9
• 小さな恋の歌 10
• for him 5
• Strawberries& cigarettes 11
• closer 3
  ...

最简单的方法：先遍历整个歌单，找出播放次数最多的歌，将这首歌添加到一个新的列表。

重复，找到播放次数第二多的歌曲。

重复，直到len(原歌单)=len(新列表)。

时间复杂度：。

代码,
Helper Function:

def findMaxNum(arr):
    MaxNum = arr[0]
    MaxNum_index = 0
    
    for i in range(1, len(arr)):
        if arr[i] > MaxNum:
            MaxNum = arr[i]
            MaxNum_index = i
    return MaxNum_index

Main Function:

def selectionSort(arr):
    newArr = []
     
    for i in range(len(arr)):
        MaxNum_index = findMaxNum(arr)
        newArr.append(arr.pop(MaxNum_index))

    return newArr