note 9 列表、时间复杂度、排序

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

列表 List

+内建(built-in)数据结构(data structure)，用来存储一系列元素(items)

如：lst = [5.4,'hello',2]

前向索引、后向索引、切片、拼接、成员、长度...

列表与字符串

+相同点

索引( [ ] 运算符)

切片( [:] )

拼接( + )和重复( * )

成员( in 运算符 )

长度( len() 函数 )

循环( for )

+不同点

使用 [ ] 生成，元素之间用逗号分隔

可以包含多种类型的对象；字符串只能是字符

内容是可变的；字符串是不可变的

列表的方法

+列表的内容是可变的

my list[0] = 'a' my list[0:2] = [1.2,3,5.6] my list.append()#追加元素改变内容 my list.extend()#追加列表 my list.insert()#任意位置插入元素 my list.pop(),my list.remove()#删除元素删除某个下标的元素 my list.remove(5)#删除元素，删除某内容 my list.sort()#排序 my list.reverse()#逆序...

读取10个数字，并计算平均数

内建函数sum

avg = sum(nums) / len(nums)

max

min

...

nums = [] for i in range(10): nums.append(float(raw_input()))avg = sum(nums) / len(nums) print avg

列表赋值

列表做函数参数

交换列表中两个元素的函数

示例：查找

1.返回下标

def search(lst,x): for i in range(len(lst)): if lst[i] == x: return i return -1lst = [10,5,8,13]print search(lst,8)

2.返回下标

index()方法

[1,2,3],index(2)

返回第一次的下标

要查找的元素不在列表中会抛出异常，ValueError: 7 is not in list

lst = [10,5,8,13]print lst.index(7)

线性查找

最坏运行时间：k0n+k1

时间复杂度

+量化一个算法的运行时间为输入长度的函数

+不需要显式的计算这些常数

如：4n+10和100n+137都与输入规模成正比

+大O表示，只保留高阶项

+线性查找的时间复杂度为：O(n)

+大O能告诉我们什么？

如果算法A的复杂度为O(n)，算法B的复杂度为O(n^2)，对于较大的输入，A总是比B快

如果算法A的复杂度为O(n)，当输入规模翻倍时，运行时间也翻倍

+大O不能告诉我们什么？

实际运行时间

对于小规模输入的行为

函数的增长率

二分查找

不一定是元素第一次出现位置的下标

def bi_search(lst,x): low = 0 high = len(lst) - 1 while low <= high: mid = (low + high) / 2 if lst[mid] == x: return mid elif lst[mid] > x: high - mid - 1 else : low = mid + 1 return - 1lst = [5,8,10,13] print bi_search(lst,5)

二分查找的时间复杂度：

排序 Sort

+将一个无序列表，按照某一顺序（由小到大或由大到小）排列

+是计算机科学中常见而且重要的任务

+有许多不同的算法，最简单直观的为以下两种

选择排序 selection sort

冒泡排序 bubble sort

选择排序

找到最小的元素

删除它，然后将其插入相应的位置

对于剩余元素，重复步骤1

def selection_sort(lst): for i in range(len(lst)): min_index = i for j in range(i + 1,len(lst)): if lst[j] < lst[min_index]: min_index = j lst.insert(i,lst.pop(min_index))lst = [10,8,5,13]selection_sort(lst)print lst

找到最小的元素

和第一个元素交换

对于剩余的元素，重复步骤1和2

def swap(lst,i,j): tmp = lst[i] lst[i] = lst[j] lst[j] = tmpdef selection_sort(lst): for i in range(len(lst)): min_index = i for j in range(i + 1,len(lst)): if lst[j] < lst[min_index]: min_index = j swap(lst,i,min_index)lst = [10,8,5,13]selection_sort(lst)print lst

选择排序的时间复杂度

冒泡排序

与选择排序类似，但是每次遍历不止交换一次

每次遍历，将最大的值排在最后

+提示：一单列表排好序，算法可以停止

def swap(lst,i,j): tmp = lst[i] lst[i] = lst[j] lst[j] = tmpdef bubble_sort(lst): top = len(lst) - 1 is_exchanged = True while is_exchanged: is_exchanged = False for i in range(top): if lst[i] > lst[i + 1]: is_exchanged = True swap(lst,i,i + 1) top -= 1lst = [12,10,8,5,13]bubble_sort(lst)print lst

时间复杂度 O(n^2)，与选择排序相同，但是通常速度更快