Python中的列表和字符串都是序列類(lèi)型做个，對(duì)字符串的一些操作在列表中同樣適合。
1.創(chuàng)建一個(gè)列表的方式：
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']
上面的表達(dá)式可以使用更簡(jiǎn)單的語(yǔ)法表示：
list1 = []
list2 = [2, 3, 4]
list3 = ["red", "green"]
list4 = [2, "three", 4] #注意：一個(gè)列表里面可以包含不同類(lèi)型的元素
2.常用的對(duì)列表的操作
其中s代表一個(gè)列表
| 操作 | 描述 |
|---|---|
| x in s | x在s序列中就返回true |
| x not in s | x不在序列s中就返回true |
| s1 + s2 | 連接兩個(gè)序列s1和s2 |
| sn, ns | n個(gè)序列s的連接 |
| s[i] | 序列的第i個(gè)元素 |
| s[i: j] | 序列下標(biāo)i到j(luò)-1的片段 |
| len（s） | 序列的長(zhǎng)度灯谣，元素個(gè)數(shù) |
| min（s） | 序列中的最小元素 |
| max（s） | 序列中的最大元素 |
| sum（s） | 序列中所有元素的和 |
| for loop | 在for循環(huán)中從左到右反轉(zhuǎn)元素 |
| >,>=,<,<=,!=,= | 比較兩個(gè)序列 |
列表可以使用random模塊中的shuffle函數(shù)隨意排列列表中的元素怠苔。
3.列表解析
可以使用‘列表解析’轉(zhuǎn)換列表中的值
例如：
>>> 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添加到列表結(jié)尾
count(x:object): int #返回元素x在列表中出現(xiàn)的次數(shù)
extend(l:list): None #將l列表中的元素添加到列表中
index(x: object): int #返回元素x在列表中第一次出現(xiàn)的下標(biāo)
insert(index: int, x:object): None #將元素x插入到列表的index處
pop(i): object #刪除指定下標(biāo)的元素并返回它吱七，如果沒(méi)有指定i刚盈，則刪除列表的最后一個(gè)元素
reverse() : None #將列表中的所有元素反轉(zhuǎn)
remove(x: object): None #刪除第一次出現(xiàn)的x
sort(): None #以升序排列列表中的元素
5.將字符串分成列表
str類(lèi)中的split方法羡洛，可指定分割的標(biāo)志。例如：
>>> items = "the weather is cold today".split()
>>> items
['the', 'weather', 'is', 'cold', 'today']
>>> items = "2016/11/6".split("/")
>>> items
['2016', '11', '6']
6.對(duì)列表元素移位處理
沒(méi)有現(xiàn)成的方法可以使用藕漱，但是可以寫(xiě)程序?qū)崿F(xiàn),例如左移一位：
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]) #結(jié)果是[2, 3, 4, 5, 1]
7. 復(fù)制列表
如果使用:
list2 = list1
實(shí)際上是將list1的引用值賦給list2欲侮，在這條語(yǔ)句之后崭闲，list2和list1指向同一個(gè)列表，而原來(lái)的list2所指向的列表就變成了垃圾（garbage）威蕉。為了將list1完全的復(fù)制給list2刁俭，可以使用：
list2 = [x for x in list1] 或簡(jiǎn)化為： list2 = [] + list1
8. 將列表當(dāng)作參數(shù)傳遞
因?yàn)榱斜硎强勺兊模诤瘮?shù)內(nèi)部可能會(huì)被改變韧涨。
9.將列表作為函數(shù)返回值
函數(shù)只會(huì)返回一個(gè)列表的引用值
10.列表的排序算法
- 選擇排序：
選擇排序先從列表中找到最小的元素和列表的第一個(gè)元素進(jìn)行交換薄翅，然后再?gòu)氖Ｓ嗟牧斜碇姓业阶钚〉脑睾褪Ｓ嗔斜淼牡谝粋€(gè)元素進(jìn)行交換，直到只剩下一個(gè)元素氓奈。
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() #結(jié)果[-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() #結(jié)果：[-4.5, 0, 1, 2, 3, 5, 9]
- 插入排序：
是將新元素重復(fù)的插入到已經(jīng)排好序的子列表中。首先取出第一個(gè)元素當(dāng)作一個(gè)已經(jīng)排好順序的子序列鼎天，然后依次從第二個(gè)開(kāi)始和前面的子序列比較并插入到適當(dāng)?shù)奈恢蒙稀?/p>
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() #結(jié)果是：[-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() #結(jié)果是[-9.8, -1, 0, 1, 2, 3, 4.5, 234, 999]
11.列表的查找算法
- 線性查找法
將關(guān)鍵字和列表中的每一個(gè)元素進(jìn)行比較舀奶。適合列表元素?cái)?shù)量較少，順序任意的情況斋射，因?yàn)楸容^簡(jiǎn)單就不給出程序?qū)崿F(xiàn)了育勺。 - 二分查找法
適合排好順序的列表。假設(shè)列表是按照升序排列的罗岖，算法解釋如下：
- 如果關(guān)鍵字小于列表中間的元素涧至，那么在列表前半部分繼續(xù)尋找關(guān)鍵字
- 如果關(guān)鍵字等于中間的元素，那么因?yàn)檎业揭粋€(gè)匹配元素而結(jié)束
- 如果關(guān)鍵字大于列表中間的元素桑包，那么在列表后半部分繼續(xù)尋找關(guān)鍵字
假設(shè)在1024（2的10次冪）個(gè)元素中查找南蓬，最壞的情況需要11（log2（n）+1）次比較，而線性查找要進(jìn)行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)
這里函數(shù)的返回值的絕對(duì)值是要查找的值應(yīng)該插入到列表中的位置赘方，并且能保持列表升序排列的位置。
