算法简介：数组、链表与选择排序
1. 数组与链表
计算机像是很多抽屉的集合体，每个抽屉都是地址。
需要将数据存储到内存时，请求计算机提供存储空间，计算机给你一个存储地址。
需要存储多项数据时，有两种基本方式：数组和链表。
1.1 数组
数组意味着所有数据在内存中是相连的。
特点：
在数组中添加新元素可能很麻烦。如果没有了空间，就得移到内存的其他地方，因此添加新元素的速度会很慢。解决方法是：预留空间。
数组的优势：随机查找。
- 你额外请求的位置可能根本用不上，这将浪费内存。你没有使用，别人也用不上。
- 数据大小超过预留空间，还得转移。
- 数组的元素带编号，编号从0而不是从1开始。元素的位置称为索引。
1.2 链表
链表中的元素可以存储在内存的任何位置。
链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
在链表中添加元素：只需将其放入内存，并将其地址存储到前一个元素中。
使用链表时，根本就不需要移动元素。因此，只要有足够的内存空间，就能为链表分配内存。
链表的优势：在插入元素方面。
需要读取所有的元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率很低。
1.3 插入和删除
常见的链表和数组操作的运行时间：
| 数组 | 链表 | |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
- 数组支持随机访问，而链表只能顺序访问。一般情况下数组用的多。
- 需要在中间插入元素时：使用链表时，插入元素只需要修改它前面的那个元素指向的地址；而使用数组时，则必须将后面的元素都向后移。如果没有足够的地址，还需要将整个数组复制到其他地方。因此当需要在中间插入元素时，链表是最好的选择。
- 当需要删除元素时，链表也是最好的选择。链表只需要修改前一个元素指向的地址即可。而数组必须将后面的元素全部前移。不同于插入，删除元素总能成功。内存中没有足够的空间，插入操作将失败，但在任何情况下都能够将元素删除。
2. 选择排序
选择排序是一种灵巧的算法，但其速度不是很快。选择排序法运行时间：O(n^2)
选择排序并非每次都需要查找n个元素，第一次查找n个元素，第二次查找n-1个元素，一次类推为：n-2,n-3…2和1.因此运行时间应该为：O(n1/2(n+1)).但是大O表示法将忽略1/2这样的常数，因此运行时间为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
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
原文地址：https://blog.csdn.net/qingttqing/article/details/136357865
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！