??深入解析链表和数组的区别?? 算法图解：第二章：选择排序
2022-04-29 14:08:41

Hello，大家好我叫是Dream呀，一个有趣的Python博主，小白一枚，多多关照 ?

入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！

最后，愿我们都能在看不到的地方闪闪发光，一起加油进步

“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~

第二章：选择排序

• ​​2.1内存的工作原理​​
• ​​2.2数组和链表​​

• ​​2.2.1链表​​
• ​​2.2.2数组​​
• ​​2.2.3术语​​
• ​​2.2.4在中间插入​​
• ​​2.2.5删除​​

• ​​2.3选择排序​​
• ​​2.4小结​​
• ​​最后的福利​​

2.1内存的工作原理

计算机就像是很多抽屉的集合体，每个抽屉都有地址。

需要将数据存储到内存时，有两种基本的存储方式：数组和链表。但他们之间也各自有缺点和优点。

2.2数组和链表

2.2.1链表

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

链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。

比如你去寻宝时，你前往地址112，那里有一张纸条，写着：下一个元素地址是558，以此类推。在链表中添加元素也很容易：只需要将其放入内存，并将地址存储到前一个元素中。

2.2.2数组

链表必须先访问元素#1才可以访问元素#2，以此类推，但如果你需要跳跃，链表的效率真的很低。

数组与此不同：你知道每个元素的地址。

需要随机读取元素时，数组的效率很高，因为可以迅速找到数组的任何元素。在链表中，元素并非靠在一起，你必须依次访问。

2.2.3术语

数组元素带有编号，编号不是从1开始，而是从0开始。

元素的位置称为索引。因此，不说“元素20的位置为1”，而是说“元素20位于索引1处”

2.2.4在中间插入

需要中间插入元素时，使用链表会更简单，只需要修改它前面的那个元素的地址指向。而是用数组时，则必须将后面的元素都向后移。

如果没有足够的空间，可能还得将整个数组复制到其他地方！因此，当需要在中间插入元素时，链表是最好的选择。

2.2.5删除

删除 链表也是最好的选择，使用数组时，删除元素后，必须将后面的元素都往前移。不同于插入，删除总能成功。

2.3选择排序

需要的总时间：O（n**2）

随着排序的进行，每次需要检查的元素在逐渐减少，最后一次需要检查的元素为1个，运行时间为啥还是O(n**2)呢？其实用大O表示法省略1/2这样的常数，可以简单的写作O（n*n）

示例代码：

#先编写一个找出数组中最小元素的函数
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):
    newArr=[]
    for i in range(len(arr)):
        smallest1=findSmallest(arr)
        newArr.append(arr.pop(smallest1))
    return newArr
print(selectionSort([8,9,5,6,4,1,2]))

2.4小结

1.计算机内存犹如一大堆抽屉

2.需要存储多个元素时，可以使用数组或者链表

3.数组的元素都在一起

4.链表的元素是分开的，其中每个元素都存储了下一个元素的地址

5.数组的读取速度很快

6.链表的插入和删除速度很快

7.在同一个数组中，所有元素的类型必须相同（都为int或者double等）。

最后的福利

☀️☀️☀️最后一点小福利带给大家：如果想快速上手python的小伙伴们，这个详细整理PPT可以迅速帮助大家打牢python基础，需要的小伙伴们可以下载一下 Python入门基础教程全套+小白速成+学不会来找我！

还有自制表白神器，需要自取：

Python表白神器，源码+解析+各种完美配置+浪漫新颖 

好啦，这就是今天要给大家分享的全部内容了

如果你喜欢的话，就不要吝惜你的一键三连了~