2、选择排序 2.1 内存的工作原理 需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。 需要存储多项数据时,有两种基本方式——数组和链表。 2.2 链表 链表的元素科存储在内存的任何地方。 链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。 在链表中添加元素很容易:只需将其放入内存,并将其地址存储到前一个元素中。 使用链表时,根本不需要移动元素。链表的优势在插入元素方面,只要有足够的内存空间,就能为链表分配内存。 2.3 数组 需要随即地读取元素时,数组的效率很高,因为可迅速找到数组的任何元素。在链表中,元素并非靠在一起的,你无法迅速计算出第五个元素的内存地址,而必须先访问第一个元素以获取第二个元素的地址,再访问第二个元素以获取第三个元素的地址,以此类推。 2.4 术语 数组的元素带编号,编号从0而不是从1开始。 元素的位置称为索引。 数组的读取时间为: 链表的读取时间为: 2.5 在中间插入 需要在中间插入元素时,数组和链表哪个更好呢?使用链表时,插入元素很简单,只需修改它前面的那个元素指向的地址。而使用数组时,则必须将后面的元素都向后移。如果没有足够的空间,可能还得将整个数组复制到其他地方。因此,当需要在中间插入元素时,链表时更好的选择。 2.6 删除 如果你要删除元素,链表也是更好的选择,因为只需修改前一个元素指向的地址即可。而使用数组时,删除元素后,必须将后面的元素都向前移。 不同于插入,删除元素总能成功。如果内存中没有足够的空间,插入操作可能失败,但在任何情况下都能将元素删除。 需要指出的是,仅当能够立即访问要删除的元素时,删除操作的运行时间才为 数组用得很多,因为它支持随机访问。 顺序访问:意味着从第一个元素开始逐个地读取元素。链表只能顺序访问:要读取链表的第十个元素,得先读取前九个元素,并沿链接找到第十个元素。 随机访问意味着可直接跳到第十个元素。 数组的读取速度更快,这是因为它们支持随机访问。很多情况都要求能够随机访问。因此数组用得很多。 数组和链表还被用来实现其他数据结构。 2.6 选择排序 大O表示法省略诸如1/2这样的常数,因此简单地写作 选择排序是一种灵巧的算法,但其速度不是很快。快速排序是一种更快的排序算法,其运行时间为 代码清单2-1 选择排序 # -*- coding: utf-8 -*- # 用于找出数组中最小元素的函数 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 print selectionSort([5, 3, 6, 2, 10])来源:http://www./content-4-172401.html |
|