Python基础总结(八)(列表List)
2016-11-07 本文已影响232人
TryEnough
Python中的列表和字符串都是序列类型,对字符串的一些操作在列表中同样适合。
1.创建一个列表的方式:
list1 = list()
list2 = list([2, 3, 4])
list3 = list(["red", "green"])
list4 = list(range(3, 6)) #[3, 4, 5]
list5 = list("abcd") #['a', 'b', 'c', 'd']
上面的表达式可以使用更简单的语法表示:
list1 = []
list2 = [2, 3, 4]
list3 = ["red", "green"]
list4 = [2, "three", 4] #注意:一个列表里面可以包含不同类型的元素
2.常用的对列表的操作
其中s代表一个列表
操作 | 描述 |
---|---|
x in s | x在s序列中就返回true |
x not in s | x不在序列s中就返回true |
s1 + s2 | 连接两个序列s1和s2 |
sn, ns | n个序列s的连接 |
s[i] | 序列的第i个元素 |
s[i: j] | 序列下标i到j-1的片段 |
len(s) | 序列的长度,元素个数 |
min(s) | 序列中的最小元素 |
max(s) | 序列中的最大元素 |
sum(s) | 序列中所有元素的和 |
for loop | 在for循环中从左到右反转元素 |
>,>=,<,<=,!=,= | 比较两个序列 |
列表可以使用random模块中的shuffle函数随意排列列表中的元素。
3.列表解析
可以使用‘列表解析’转换列表中的值
例如:
>>> list1 = [x for x in range(5)]
>>> list1
[0, 1, 2, 3, 4]
>>> list2 = [0.5 * x for x in list1]
>>> list2
[0.0, 0.5, 1.0, 1.5, 2.0]
>>> list3 = [x for x in list2 if x < 1.5]
>>> list3
[0.0, 0.5, 1.0]
4. 列表常用的方法
append(x: object): None #将元素x添加到列表结尾
count(x:object): int #返回元素x在列表中出现的次数
extend(l:list): None #将l列表中的元素添加到列表中
index(x: object): int #返回元素x在列表中第一次出现的下标
insert(index: int, x:object): None #将元素x插入到列表的index处
pop(i): object #删除指定下标的元素并返回它,如果没有指定i,则删除列表的最后一个元素
reverse() : None #将列表中的所有元素反转
remove(x: object): None #删除第一次出现的x
sort(): None #以升序排列列表中的元素
5.将字符串分成列表
str类中的split方法,可指定分割的标志。例如:
>>> items = "the weather is cold today".split()
>>> items
['the', 'weather', 'is', 'cold', 'today']
>>> items = "2016/11/6".split("/")
>>> items
['2016', '11', '6']
6.对列表元素移位处理
没有现成的方法可以使用,但是可以写程序实现,例如左移一位:
def shift(list):
temp = list[0]
for i in range(1, len(list)):
list[i - 1] = list[i]
list[len(list) - 1] = temp
print(list)
shift([1,2,3,4,5]) #结果是[2, 3, 4, 5, 1]
7. 复制列表
如果使用:
list2 = list1
实际上是将list1的引用值赋给list2,在这条语句之后,list2和list1指向同一个列表,而原来的list2所指向的列表就变成了垃圾(garbage)。为了将list1完全的复制给list2,可以使用:
list2 = [x for x in list1] 或简化为: list2 = [] + list1
8. 将列表当作参数传递
因为列表是可变的,在函数内部可能会被改变。
9.将列表作为函数返回值
函数只会返回一个列表的引用值
10.列表的排序算法
- 选择排序:
选择排序先从列表中找到最小的元素和列表的第一个元素进行交换,然后再从剩余的列表中找到最小的元素和剩余列表的第一个元素进行交换,直到只剩下一个元素。
def selectionSort(lst):
for i in range(len(lst) - 1):
currentMin = lst[i]
currentMinIndex = i
for j in range(i + 1, len(lst)):
if currentMin > lst[j]:
currentMin = lst[j]
currentMinIndex = j
if currentMinIndex != i:
lst[currentMinIndex] = lst[i]
lst[i] = currentMin
return lst
def main():
lst = [1, 3, 2,0,9,8.9, -1.0, -9.8, 4.5]
print(selectionSort(lst))
main() #结果[-9.8, -1.0, 0, 1, 2, 3, 4.5, 8.9, 9]
选择排序递归算法:
def selectionSort(lst):
sortHelper(lst, 0, len(lst) - 1)
def sortHelper(lst, low, high):
if low < high:
indexOfMin = low
min = lst[low]
for i in range(low + 1, high + 1):
if lst[i] < min:
min = lst[i]
indexOfMin = i
lst[indexOfMin] = lst[low]
lst[low] = min
sortHelper(lst, low + 1, high)
def main():
lst = [3, 2, 1, 5, 9, 0, -4.5]
selectionSort(lst)
print(lst)
main() #结果:[-4.5, 0, 1, 2, 3, 5, 9]
- 插入排序:
是将新元素重复的插入到已经排好序的子列表中。首先取出第一个元素当作一个已经排好顺序的子序列,然后依次从第二个开始和前面的子序列比较并插入到适当的位置上。
def insertionSort(lst):
for i in range(1, len(lst)):
currentElement = lst[i]
k = i - 1
while k >= 0 and lst[k] > currentElement:
lst[k + 1] = lst[k]
k -= 1
lst[k + 1] = currentElement
return lst
def main():
lst = [1, 3, 2,0,9,8.9, -1.0, -9.8, 4.5]
print(insertionSort(lst))
main() #结果是:[-9.8, -1.0, 0, 1, 2, 3, 4.5, 8.9, 9]
- 快速排序算法:
#array's quick sort
def quickSort(arr,i,j):
if i < j:
base = quick(arr, i, j)
quickSort(arr, i, base)
quickSort(arr, base+1, j)
return arr
def quick(arr, i, j):
base = arr[i]
while i < j:
while i < j and arr[j] > base:
j-=1
while i < j and arr[j] < base:
arr[i] = arr[j]
i+=1
arr[j] = arr[i]
arr[i] = base
return i
def main():
lst = [1, 3, 2, -1, 4.5, 999, 234, 0, -9.8]
print(quickSort(lst, 0, len(lst)-1))
main() #结果是[-9.8, -1, 0, 1, 2, 3, 4.5, 234, 999]
11.列表的查找算法
- 线性查找法
将关键字和列表中的每一个元素进行比较。适合列表元素数量较少,顺序任意的情况,因为比较简单就不给出程序实现了。 - 二分查找法
适合排好顺序的列表。假设列表是按照升序排列的,算法解释如下:
- 如果关键字小于列表中间的元素,那么在列表前半部分继续寻找关键字
- 如果关键字等于中间的元素,那么因为找到一个匹配元素而结束
- 如果关键字大于列表中间的元素,那么在列表后半部分继续寻找关键字
假设在1024(2的10次幂)个元素中查找,最坏的情况需要11(log2(n)+1)次比较,而线性查找要进行1023次比较。显然二分查找更加高效:
def binarySearch(list, key):
low = 0
high = len(list) - 1
while high >= low:
mid = (low + high) // 2
if key < list[mid]:
high = mid - 1
elif key == list[mid]:
return mid
else:
low = mid + 1
return -low - 1
list = [-9.8, -1.0, 0, 1, 2, 3, 4.5, 8.9, 9]
i = binarySearch(list, 6)
print(i)
这里函数的返回值的绝对值是要查找的值应该插入到列表中的位置,并且能保持列表升序排列的位置。