链表的优势在插入元素方面
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
来自<百度百科>
链表跳跃读取元素时,需要依次访问该元素前的元素(获得下个元素地址),降低了效率.数组中的元素是连在一起的,知道每一个元素的地址,容易做到跳跃读取元素
所谓数组,是有序的元素序列。若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中,为了处理方便, 把具有相同类型的若干元素按无序的形式组织起来的一种形式。这些无序排列的同类数据元素的集合称为数组。
来自<百度百科>
常见的数组和链表操作运行时间
- | 数组 | 链表 |
---|---|---|
读取 | \(O _{(1)}\) | \(O _{(n)}\) |
插入 | \(O _{(n)}\) | \(O _{(1)}\) |
删除 | \(O _{(n)}\) | \(O _{(1)}\) |
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
来自<百度百科>
随着排序的进行,每次需要检查的元素数在减少,最后一次需要检查的元素都只有一个,检查元素数依次为n-1,n-2,...,2,1.平均检查的元素为\(\frac{n}{2}\),因此运行时间为\(O _{(\frac{n}{2})}\).但大O表示法省略了诸如\(\frac{n}{2}\)这样的常数
python代码:
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = min(arr)
newArr.append(smallest)
arr.remove(smallest)
return newArr
myList = [5,3,25,6,9,11,1]
print(selectionSort(myList))
在同一个数组中,所有的元素的类型都必须相同
原文:https://www.cnblogs.com/wangbaby/p/10290759.html