1、内存工作原理
今天你要去丹尼斯购物，但你带了雨伞和包，丹尼斯要求这些东西不能带进商场，所以你只能到存储柜存放这些物品...
存储柜有很多柜子，每个柜子都有地址，假设一个箱子只能存放一个物品，你就需要两个箱子存放伞和包
你将伞和包分别放进相邻的两个柜子中，这时存储柜吐出纸条上面写着，你放物品的柜子地址
以防你找不到物品
其实计算机的内存就像是个大型存储柜，里面有很多小柜子，每个柜子都有自己的地址
需要将数据存储到内存时，你请求计算机，它将给你一个存储地址，你将数据存进对应的位置
在存储多项数据时，有两种基本存储方式 数组和链表
2，数组和链表
数组是线性相连的，比如你想将4个数据以数组的形式，放入内存中，计算机会返回给你4个相连的存储地址，用来把4个数据线性的放在对应的位置中
看起来很完美？
但这里有一个问题，假如 内存中 1 -2- 3 号地址，都没有存放数据，但4号存放了数据，很尴尬，你的数组数据无法存放1 2 3 号对应的位置，因为你要放4个数据，并且数组要求数据必须相连，如果放了1 -2- 3的位置，4被其他数据占用，数组中最后的数据只能放5号，这是做不到的，数组要求，数据要连续相连存储...所以你只能放在4后面，也就是 5-6-7-8的位置，1-2-3还空着...资源被浪费了
另一个问题，数组存储是相连的，如果长度为4的数组存储在内存中，而末位相邻的内存中存储了其他数据，此时添加一个数据会怎样?
很抱歉，数组就像是4个相连的抽屉，第五个位置被其他数据占用，第五个放不进去，那怎么办，只能重新创建一个5个相连的抽屉，然后放进5个数据（把原来的4个取出来，放到新的里面）...这意味着，要么你很清楚有多少数据，精确的设置数组长度，要么你多加长度（多加几个抽屉），以应不便，这就像我邀请10个朋友吃饭，有朋友说他也会带2-4个朋友来，具体几个他也不知道...所以，在长桌上，你准备几把椅子呢？至少14把...结果当天朋友只带来了一个...所以多出来的3把椅子就浪费了
申请更多数据存储空间，有可能造成浪费...
这就是数组的缺点...数据是依次相连，次序是固定的，所以，想要调整数据位置或者插入数据并不容易
链表
链表中的元素可以存储在内存中的任何位置
链表中的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起
因此链表扩容很简单，只需将数据放入内存，并将其地址存储到上个元素中
链表的优势就在于插入元素方便简单，内存利用度极高
看起来很完美？
如果一个链表存储了5个数据，我取出最后一个数据，我必须要从第一个链表元素，找到第二个链表元素的地址，找到第2个元素，查找第三个链表的地址，直到找到第四个元素，我才知道第五个元素的地址，才能取出数据....
链表的数据存储在内存中地址不是相连的（存放在内存中的任意位置），所以我们只能从头开始查找下个位置的元素，直到找到我们想要的。
链表：查找效率很低，插入元素方便
数组存储在内存中的地址是依次相连，我们知道起始位，其他的位置也就知道了，这样我们就可以很方便的取出我们想要位置的数据
数组：查询效率高，但扩容插入艰难
术语
数组中的元素是带编号的 从0开始，依据位置依次加1 （这里是编号，不是内存地址）
比如 数组 ——10—— 20 —— 30 —— 40
编号 —— 0 —— 1 —— 2 —— 3
从0开始，而不是1，这是因为从开始可以让数组代码编写起来更加容易，所有就从0开始
编号的官方称呼为 索引，请记住 索引 即为位置，例如 元素20的索引是1
在中间插入
数组 [0 ,1, 2 ,3 ,4 ]
索引 [0 ,1, 2 ,3 ,4 ]
我们想在 索引 1 处插入元素 0.5
插入后
数组 [0 , 0.5，1, 2 ,3 ,4 ]
索引 [0 , 1， 2, 3 ,4 ,5 ]
插入0.5后，索引1后面的所有元素，都必须向后挪动1个位置...
极端情况下，数组（长度是5）所在内存区域第6个位置被其他数据占有，没有足够的空间进行插入，
那就需要将整个数据复制到能够存放连续6个元素的内存区域中去
链表 0——>1——>2——>3——>4
我们想在0-1间插入 0.5
那只需要将 0的箭头（下个元素的存储地址）指向0.5 0——>0.5
同时将0.5的箭头指向1（0.5中存储1的地址） 0.5——>1
so
对于插入 数组的时间复杂度为 O(n) 链表的 为O（1）
删除
数组 [0 ,1, 2 ,3 ,4 ]
索引 [0 ,1, 2 ,3 ,4 ]
我们想删除索引0处的元素
删除后
数组 [1, 2 ,3 ,4 ]
索引 [0 ,1, 2 ,3 ]
0索引后面的元素依次向前移动1
链表 0——>1——>2——>3——>4
我想删除 元素0
请直接删除... 记录1 为起始元素即可
so 对于删除 数组的时间复杂度为 O(n) 链表的 为O（1）
链表擅长插入和删除
数组擅长查看访问
选择排序
方法：每次挑出元素中最大（或最小）的元素，然后排序
例如 数组 4-9-5-6-7 由大到小排列
第一次 选出9 [9] 剩余4-5-6-7
第二次 选出7 [9,7] 剩余4-5-6
第三次 选出6 [9,7,6] 剩余4-5
第四次 选出5 [9,7,6,5] 剩余4
第五次 选出4 [9,7,6,5,4]
# 选择排序===============================================
# 1. 使用交换方法，将原有数组进行从大到小的排列
def selection_sort(array):
length = len(array)
for i in range(length):
max_ = array[i]
max_index = i
for k in range(i + 1, length):
if max_ < array[k]:
max_ = array[k]
max_index = k
# 交换位置
if max_index != i:
small = array[i]
array[i] = max_
array[max_index] = small
print(array)
# 选择排序===============================================
# 2.使用数据
def selection_sort_n(array):
new_array = []
for i in range(len(array)):
index = findMaxIndex(array)
new_array.append(array.pop(index))
print(new_array)
def findMaxIndex(array):
max_index = 0
max_value = array[0]
for i in range(1, len(array)):
if max_value < array[i]:
max_index = i
max_value = array[i]
return max_index
if __name__ == '__main__':
selectionSort = [10, 8, 33, 26, 11, 5, 55]
print(selectionSort)
selection_sort(selectionSort)
selectionSort = [10, 8, 33, 26, 11, 5, 55]
selection_sort_n(selectionSort)
总结
1.数据可以数组和链表的形式存储在内存中
2.数组的元素是有序相邻的
3.链表的元素是分开的，其每个元素存储着下个元素的地址
4.数组的读取速度很快
5.链表的插入删除速度很快
6.在同一个数组中，所以元素都必须是同一类型（都是int 或 double）
