1.算法復(fù)雜度的度量
1.1 對(duì)于List
1.2 對(duì)于字典
2. 基本數(shù)據(jù)結(jié)構(gòu)類型
2.1 棧
棧的排序原則：LIFO 后進(jìn)先出
Stack()：創(chuàng)建一個(gè)新的空棧廊佩。它不需要參數(shù)阅束，并返回一個(gè)空棧壁榕。
Push(item)：將新項(xiàng)添加到堆棧的頂部伏嗜。它需要參數(shù) item 并且沒有返回值。
pop()：從棧頂刪除項(xiàng)目汉买。它不需要參數(shù),返回 item壤蚜。棧被修改悼瓮。
peek()：返回棧頂?shù)捻?xiàng)，不刪除它硼啤。它不需要參數(shù)议经。堆棧不被修改。
isEmpty()：測(cè)試看棧是否為空谴返。它不需要參數(shù)煞肾，返回一個(gè)布爾值。
size()：返回棧的項(xiàng)目數(shù)嗓袱。它不需要參數(shù)籍救，返回一個(gè)整數(shù)。
2.2 隊(duì)列(Queue)
先進(jìn)先出（FIFO）
隊(duì)列的基本操作：
● Queue()創(chuàng)建一個(gè)空隊(duì)列對(duì)象索抓，無(wú)需參數(shù)钧忽，返回空的隊(duì)列；
● enqueue(item)將數(shù)據(jù)項(xiàng)添加到隊(duì)尾逼肯，無(wú)返回值耸黑；
● dequeue()從隊(duì)首移除數(shù)據(jù)項(xiàng)，無(wú)需參數(shù)篮幢，返回值為隊(duì)首數(shù)據(jù)項(xiàng)大刊；
● isEmpty()測(cè)試是否為空隊(duì)列，無(wú)需參數(shù)三椿，返回值為布爾值缺菌；
● size()返回隊(duì)列中的數(shù)據(jù)項(xiàng)的個(gè)數(shù)，無(wú)需參數(shù)搜锰。
在Python中實(shí)現(xiàn)隊(duì)列：
Class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self, item):
self.items.pop()
def size(self):
return len(self.items)
q = Queue()
q.enqueue('dog')
q.enqueue(4)
print(q.size())
熱土豆問(wèn)題的模擬實(shí)現(xiàn)：
from pythonds.basic.queue import Queue
def hotPotato(namelist, num):
simqueue = Queue()
for name in namelist:
simqueue.enqueue(name)
while simqueue.size() > 1:
for i in range(num):
simqueue.enqueue(simqueue.dequeue())
simqueue.dequeue()
return simqueue.dequeue()
print(hotPotato(["Alice", "Bob", "Cindy", "David", "Ella", "France"], 7))
打印任務(wù)的實(shí)現(xiàn)：
import random
from pythonds.basic.queue import Queue
class Printer:
def __init__(self, ppm):
self.pagerate = ppm
self.currentTask = None
self.timeRemaining = 0
def tick(self):
if self.currentTask != None:
self.timeRemaining = self.timeRemaining - 1
if self.timeRemaining <= 0:
self.currentTask = None
def busy(self):
if self.currentTask != None:
return True
else:
return False
def startNext(self, newtask):
self.currentTask = newtask
self.timeRemaining = newtask.getPages() * 60 / self.pagerate
class Task:
def __init__(self, time):
self.timestamp = time
self.pages = random.randrange(1, 21)
def getStamp(self):
return self.timestamp
def getPages(self):
return self.pages
def waitTime(self, currenttime):
return currenttime - self.timestamp
def simulation(numSeconds, pagesPerMinute):
labprinter = Printer(pagesPerMinute)
printQueue = Queue()
waitingtimes = []
for currentSecond in range(numSeconds):
if newPrintTask():
task = Task(currentSecond)
printQueue.enqueue(task)
if (not labprinter.busy()) and (not printQueue.isEmpty()):
nexttask = printQueue.dequeue()
waitingtimes.append(nexttask.waitTime(currentSecond))
labprinter.startNext(nexttask)
labprinter.tick()
averageWait = sum(waitingtimes) / len(waitingtimes)
print("Average Wait %6.2f secs %3d tasks remaining." % (averageWait, printQueue.size()))
def newPrintTask():
# 產(chǎn)生一個(gè)新的打印任務(wù)的概率
num = random.randrange(1, 181)
if num == 180:
return True
else:
return False
for i in range(10):
simulation(3600, 5)
2.2 雙端隊(duì)列(deque 或 double-ended queue)
元素可以從兩端插入伴郁，也可以從兩端刪除。 可以說(shuō)蛋叼，
雙端隊(duì)列這種混合的線性數(shù)據(jù)結(jié)構(gòu)擁有棧和隊(duì)列各自擁有的所有功能
雙端隊(duì)列的基本操作：
- Deque() 創(chuàng)建一個(gè)空雙端隊(duì)列焊傅，無(wú)參數(shù)，返回值為 Deque 對(duì)象狈涮。
- addFront(item) 在隊(duì)首插入一個(gè)元素狐胎，參數(shù)為待插入元素，無(wú)返回值歌馍。
- addRear(item) 在隊(duì)尾插入一個(gè)元素握巢，參數(shù)為待插入元素，無(wú)返回值
- removeFront() 在隊(duì)首移除一個(gè)元素松却，無(wú)參數(shù)暴浦，返回值為該元素溅话。雙端隊(duì)列會(huì)被改變。
- removeRear() 在隊(duì)尾移除一個(gè)元素肉渴，無(wú)參數(shù)公荧，返回值為該元素。雙端隊(duì)列會(huì)被改變同规。
- isEmpty() 判斷雙端隊(duì)列是否為空循狰，無(wú)參數(shù)，返回布爾值券勺。
- size() 返回雙端隊(duì)列中數(shù)據(jù)項(xiàng)的個(gè)數(shù)绪钥，無(wú)參數(shù)，返回值為整型數(shù)值
python實(shí)現(xiàn)雙端隊(duì)列：
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0, item)
def removeFront(self):
self.items.pop()
def removeRear(self):
self.items.pop(0)
def size(self):
return len(self.items)
回文判斷函數(shù)的實(shí)現(xiàn)：
from pythonds.basic.deque import Deque
def palchecker(aString):
chardeque = Deque()
for ch in aString:
chardeque.addRear(ch)
stillEqual = True
while chardeque.size() > 1 and stillEqual:
first = chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False
return stillEqual
2.3 無(wú)序列表
無(wú)序列表是一些元素的集合关炼，每個(gè)元素?fù)碛幸粋€(gè)與其它元素不同的相對(duì)位置程腹。
常用的方法有：
- list() 創(chuàng)建一個(gè)新的空列表。它不需要參數(shù)儒拂，而返回一個(gè)空列表寸潦。
- add(item) 將新項(xiàng)添加到列表，沒有返回值社痛。假設(shè)元素不在列表中见转。
- remove(item) 從列表中刪除元素。需要一個(gè)參數(shù)蒜哀，并會(huì)修改列表斩箫。此處假設(shè)元
素在列表中。 - search(item) 搜索列表中的元素撵儿。需要一個(gè)參數(shù)乘客，并返回一個(gè)布爾值。
- isEmpty() 判斷列表是否為空淀歇。不需要參數(shù)易核，并返回一個(gè)布爾值。
- size() 返回列表的元素?cái)?shù)浪默。不需要參數(shù)牡直，并返回一個(gè)整數(shù)。
- append(item) 在列表末端添加一個(gè)新的元素浴鸿。它需要一個(gè)參數(shù)井氢，沒有返回值弦追。
- index(item) 返回元素在列表中的位置岳链。它需要一個(gè)參數(shù)，并返回位置索引值劲件。
- insert(pos,item) 在指定的位置添加一個(gè)新元素掸哑。它需要兩個(gè)參數(shù)约急，沒有返回值。
- pop() 從列表末端移除一個(gè)元素并返回它苗分。它不需要參數(shù)厌蔽，返回一個(gè)元素。假設(shè)列表至少有一個(gè)元素摔癣。
- pop(pos) 從指定的位置移除列表元素并返回它奴饮。它需要一個(gè)位置參數(shù)，并返回一個(gè)元素择浊。假設(shè)該元素在列表中戴卜。
為了實(shí)現(xiàn)無(wú)序列表绰咽，我們將構(gòu)建一個(gè)鏈表
????需要注意的是史侣，該列表的第一項(xiàng)的位置必須被明確指出撼班。一旦我們知道第一項(xiàng)是什么牺汤，第一項(xiàng)就可以告訴我們第二項(xiàng)是什么织阳，以此類推椭蹄。從外部指向的第一項(xiàng)通常被稱為鏈表的頭戏锹。同樣地斜棚，鏈表的最后一項(xiàng)需要告訴我們有沒有下一個(gè)項(xiàng)目糕篇。
??????用鏈表實(shí)現(xiàn)的基本模塊是節(jié)點(diǎn)啄育。每個(gè)節(jié)點(diǎn)對(duì)象必須持有至少兩條信息。首先娩缰，節(jié)點(diǎn)必須包含列表元素本身灸撰。我們將這稱為該節(jié)點(diǎn)的“數(shù)據(jù)區(qū)”（data field）。此外拼坎，每個(gè)節(jié)點(diǎn)必須保持到下一個(gè)節(jié)點(diǎn)的引用浮毯。
python實(shí)現(xiàn)節(jié)點(diǎn)：
class Node:
def __init__(self, initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self, newdata):
self.data = newdata
def setNext(self, newnext):
self.next = newnext
python實(shí)現(xiàn)無(wú)序列表：
class Node:
def __init__(self, initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self, newdata):
self.data = newdata
def setNext(self, newnext):
self.next = newnext
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def add(self, item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def size(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.getNext()
return count
def search(self, item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def remove(self, item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
# 要移除的是第一個(gè)元素的情況
if previous == None:
self.head = current.getNext()
# 要移除的是最后一個(gè)元素的情況
elif current == None:
previous.setNext(None)
else:
previous.setNext(current.getNext())
def append(self, item):
current = self.head
previous = None
# 列表為空時(shí)
if current == None:
last_item = Node(item)
last_item.setNext(self.head)
self.head = last_item
else:
while current != None:
previous = current
current = current.getNext()
last_item = Node(item)
previous.setNext(last_item)
def insert(self, index, item):
current = self.head
previous = None
count = 0
# 先對(duì)index有沒有超過(guò)list長(zhǎng)度進(jìn)行判斷
if index > self.size():
raise IndexError
else:
while count != index:
count += 1
previous = current
current = current.getNext()
# 說(shuō)明是在開頭位置插入元素
if previous == None:
insert_item = Node(item)
insert_item.setNext(self.head)
self.head = insert_item
# 說(shuō)明是在list結(jié)尾插入元素
else:
insert_item = Node(item)
insert_item.setNext(current)
previous.setNext(insert_item)
def index(self, item):
current = self.head
count = 0
found_flag = True
while current.getData() != item:
count += 1
current = current.getNext()
if current == None:
found_flag = False
break
if found_flag:
return count
else:
return None
def pop(self, index=None):
if index == None:
index = self.size() - 1
current = self.head
count = 0
previous = None
# 先判斷index是否超出范圍
if (index >= 0 and index > self.size() - 1) or (index < 0 and index + self.size() > self.size()):
raise IndexError
else:
if index >= 0:
while index != count:
count += 1
previous = current
current = current.getNext()
else:
while index + self.size() != count:
count += 1
previous = current
current = current.getNext()
# 說(shuō)明刪除的是第一個(gè)元素
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
return current
mylist = UnorderedList()
mylist.append(12)
mylist.insert(0, 2)
mylist.append(15)
mylist.pop()
2.4 有序列表
有序列表的方法：
- OrderedList()：創(chuàng)建一個(gè)新的空有序列表。它返回一個(gè)空有序列表并且不需要傳遞任何參數(shù)泰鸡。
- add(item):在保持原有順序的情況下向列表中添加一個(gè)新的元素债蓝，新的元素作為參數(shù)傳遞進(jìn)函數(shù)而函數(shù)無(wú)返回值。假設(shè)列表中原先并不存在這個(gè)元素盛龄。
- remove(item):從列表中刪除某個(gè)元素饰迹。欲刪除的元素作為參數(shù)，并且會(huì)修改原列表余舶。假設(shè)原列表中存在欲刪除的元素啊鸭。
- search(item)：在列表中搜索某個(gè)元素，被搜索元素作為參數(shù)匿值，返回一個(gè)布爾值赠制。
- isEmpty()：測(cè)試列表是否為空，不需要輸入?yún)?shù)并且其返回一個(gè)布爾值挟憔。
- size()：返回列表中元素的數(shù)量钟些。不需要參數(shù)烟号，返回一個(gè)整數(shù)。
- index(item)：返回元素在列表中的位置政恍。需要被搜索的元素作為參數(shù)輸入汪拥，返回此元素的索引值。假設(shè)這個(gè)元素在列表中篙耗。
- pop()：刪除并返回列表中的最后一項(xiàng)迫筑。不需要參數(shù)，返回刪除的元素宗弯。假設(shè)列表中至少有一個(gè)元素铣焊。
- pop(pos)：刪除并返回索引 pos 指定項(xiàng)。需要被刪除元素的索引值作為參數(shù)罕伯，并且返回這個(gè)元素曲伊。假設(shè)該元素在列表中
python實(shí)現(xiàn)有序列表：
class OrderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def add(self, item):
current = self.head
previous = None
stop = False
while current is not None and not stop:
if current.getData() > item:
stop = True
else:
previous = current
current = current.getNext()
temp = Node(item)
if previous is None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(current)
previous.setNext(temp)
def size(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.getNext()
return count
def search(self, item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
def remove(self, item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
# 要移除的是第一個(gè)元素的情況
if previous == None:
self.head = current.getNext()
# 要移除的是最后一個(gè)元素的情況
elif current == None:
previous.setNext(None)
else:
previous.setNext(current.getNext())
def append(self, item):
current = self.head
previous = None
# 列表為空時(shí)
if current == None:
last_item = Node(item)
last_item.setNext(self.head)
self.head = last_item
else:
while current != None:
previous = current
current = current.getNext()
last_item = Node(item)
previous.setNext(last_item)
def insert(self, index, item):
current = self.head
previous = None
count = 0
# 先對(duì)index有沒有超過(guò)list長(zhǎng)度進(jìn)行判斷
if index > self.size():
raise IndexError
else:
while count != index:
count += 1
previous = current
current = current.getNext()
# 說(shuō)明是在開頭位置插入元素
if previous == None:
insert_item = Node(item)
insert_item.setNext(self.head)
self.head = insert_item
# 說(shuō)明是在list結(jié)尾插入元素
else:
insert_item = Node(item)
insert_item.setNext(current)
previous.setNext(insert_item)
def index(self, item):
current = self.head
count = 0
found_flag = True
while current.getData() != item:
count += 1
current = current.getNext()
if current == None:
found_flag = False
break
if found_flag:
return count
else:
return None
def pop(self, index=None):
if index == None:
index = self.size() - 1
current = self.head
count = 0
previous = None
# 先判斷index是否超出范圍
if (index >= 0 and index > self.size() - 1) or (index < 0 and index + self.size() > self.size()):
raise IndexError
else:
if index >= 0:
while index != count:
count += 1
previous = current
current = current.getNext()
else:
while index + self.size() != count:
count += 1
previous = current
current = current.getNext()
# 說(shuō)明刪除的是第一個(gè)元素
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
return current
2.5 鏈表的算法分析
???????當(dāng)分析鏈表方法的復(fù)雜度時(shí)，我們應(yīng)該考慮它們是否需要遍歷鏈表追他》啬迹考慮一個(gè)有 n 個(gè)節(jié)點(diǎn)的鏈表， isEmpty 方法復(fù)雜度是 O（1）邑狸，因?yàn)樗恍枰獧z查鏈表的頭指針是否為 None懈糯。對(duì)于方法 size，則總需要 n 個(gè)步驟单雾，因?yàn)槌吮闅v整個(gè)鏈表以外赚哗，沒有辦法知道鏈表的節(jié)點(diǎn)數(shù)。因此硅堆， size 方法的復(fù)雜度是 O（n）屿储。無(wú)序列表的 add 方法的復(fù)雜度是 O（1），因?yàn)槲覀冇肋h(yuǎn)只需要在鏈表的頭部簡(jiǎn)單地添加一個(gè)新的節(jié)點(diǎn)渐逃。但是够掠， search、 remove 和在有序列表中的 add 方法茄菊，需要遍歷疯潭。盡管在平均情況下，它們可能只需要遍歷一半的節(jié)點(diǎn)面殖，但這些方法的復(fù)雜度都是 O(n)竖哩，因?yàn)樵谧钤愀獾那闆r下需要遍歷整個(gè)鏈表。
???????你可能還注意到脊僚， 這些方法的實(shí)現(xiàn)性能與 Python 的內(nèi)置列表 list 不同相叁，這表明 Python 中的 list不是這么實(shí)現(xiàn)的。實(shí)際上， Python 中的列表的實(shí)現(xiàn)是基于數(shù)組的
2.6 小結(jié)
線性數(shù)據(jù)結(jié)構(gòu)以有序的方式維持它們的數(shù)據(jù)钝荡。
棧（Stack）是具有后進(jìn)先出（LIFO）特性的有序的簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)。
棧（Stack）的基本操作是 push舶衬， pop 和 isEmpty埠通。
隊(duì)列（Queue）是具有先進(jìn)先出（FIFO）特性的有序的簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)。
隊(duì)列（Queue）的基本操作是 enqueue,dequeue 和 isEmpty逛犹。
前綴表達(dá)式端辱，中綴表達(dá)式和后綴表達(dá)式都是書寫表達(dá)式的方式。
棧（Stacks）對(duì)于設(shè)計(jì)算法并求值以及轉(zhuǎn)化表達(dá)式非常有效虽画。
棧（Stacks）具有反轉(zhuǎn)的特性舞蔽。
隊(duì)列（Queue）可以幫助構(gòu)建時(shí)序仿真。
模擬實(shí)驗(yàn)使用隨機(jī)數(shù)生成器來(lái)創(chuàng)建一個(gè)真實(shí)的環(huán)境從而使我們回答“假設(shè)”類型的問(wèn)題码撰。
雙端隊(duì)列（Deque）是允許像棧和隊(duì)列一樣的混合行為的數(shù)據(jù)結(jié)構(gòu)渗柿。
雙端隊(duì)列（Deque）的基本操作是 addFront, addRear, removeFront, removeRear 和 isEmpty。
列表（List）是具有相對(duì)位置的元素的集合脖岛。
鏈表的實(shí)現(xiàn)保持邏輯順序而不要求數(shù)據(jù)項(xiàng)依次存放在連續(xù)的存儲(chǔ)空間朵栖。
對(duì)鏈表表頭的修改是一種特殊情況
3. 遞歸
3.1遞歸三大定理：
- 遞歸算法必須有個(gè)基本結(jié)束條件
- 遞歸算法必須改變自己的狀態(tài)并向基本結(jié)束條件演進(jìn)
- 遞歸算法必須遞歸地調(diào)用自身
將 整 數(shù) 轉(zhuǎn) 化 成 任 意 進(jìn) 制 表 示 的 字 符 串 形 式：
def to_str(n, base):
convert_string = '0123456789ABCDEF'
if n < base:
return convert_string[n]
else:
return to_str(n // base, base) + convert_string[n % base]
print(to_str(10, 2))
棧幀：實(shí)現(xiàn)遞歸
from pythonds.basic.stack import Stack
r_stack = Stack()
def to_str(n, base):
convert_string = '0123456789ABCDEF'
while n > 0:
if n < base:
r_stack.push(convert_string[n])
else:
r_stack.push(convert_string[n % base])
n = n // base
res = ""
while not r_stack.isEmpty():
res = res + str(r_stack.pop())
return res
print(to_str(1453, 16))
3.2 圖示遞歸：
python繪制遞歸圓形
import turtle
myTurtle = turtle.Turtle()
myWin = turtle.Screen()
def drawSprial(myTurtle, radius, angle):
if angle > 0:
myTurtle.circle(radius)
myTurtle.left(30)
drawSprial(myTurtle, radius, angle - 30)
drawSprial(myTurtle, 100, 360)
myWin.exitonclick()
python繪制分形樹
import turtle
def tree(branchLen, t):
if branchLen > 5:
t.forward(branchLen)
# print(1, branchLen)
t.right(20)
tree(branchLen - 15, t)
# print(2, branchLen)
t.left(40)
tree(branchLen - 10, t)
# print(3, branchLen)
t.right(20)
t.backward(branchLen)
def main():
t = turtle.Turtle()
myWin = turtle.Screen()
t.left(90)
t.up()
t.backward(100)
t.down()
t.color("green")
tree(75, t)
myWin.exitonclick()
main()
4. 搜索與排序
4.1搜索
4.1.1順序搜索
python實(shí)現(xiàn)順序搜索
def sequentialSearch(alist, item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos += 1
return found
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 0))
有序列表的順序搜索
def sequentialSearch(alist, item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos += 1
return found
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 0))
4.1.2 二分法搜索
二分法搜索一個(gè)有序表
def binarySearch(alist, item):
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
midpoint = (first + last) // 2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1
return found
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarySearch(testlist, 42))
遞歸實(shí)現(xiàn)二分法：
def binarySearch(alist, item):
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
midpoint = (first + last) // 2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1
return found
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarySearch(testlist, 42))
二分法搜索的復(fù)雜度是O(log(n))，因?yàn)楸葘?duì)的次數(shù)為 n/2^i=1柴梆，解得i = log(n)陨溅。
即使二分搜索通常比順序搜索要好，值得注意的是绍在，對(duì)于較小的n值门扇，排序所附加的消耗可能是不值得的。事實(shí)上偿渡，我們應(yīng)當(dāng)一致考慮進(jìn)行額外的排序工作來(lái)得到搜索優(yōu)勢(shì)是否是有效開銷臼寄。如果我們可以排序一次然后搜索許多次，排序開銷并不是那么顯著溜宽。然而脯厨，對(duì)于大列表，哪怕是一次排序的消耗也可能是巨大的坑质，從一開始簡(jiǎn)單執(zhí)行順序搜索也許是最好的選擇合武。
4.1.3 散列
???????我們將嘗試進(jìn)一步建立一種新的數(shù)據(jù)結(jié)構(gòu)，基于他的搜索算法的時(shí)間復(fù)雜度為O(1)涡扼。這個(gè)概念被稱為散列稼跳。
???????散列表的每一個(gè)位置叫做槽，能夠存放一個(gè)數(shù)據(jù)項(xiàng)吃沪，并以從0開始遞增的整數(shù)命名汤善。在初始條件下，散列表中是沒有任何數(shù)據(jù)的，即每個(gè)槽都是空的红淡。我們可以利用列表實(shí)現(xiàn)一個(gè)散列表不狮，它的每一個(gè)元素都被初始化為None。
???????某個(gè)數(shù)據(jù)項(xiàng)與在散列表中存儲(chǔ)它的槽之間的映射叫做散列函數(shù)在旱。將數(shù)據(jù)傳入散列函數(shù)計(jì)算得出的是這個(gè)數(shù)據(jù)儲(chǔ)存在散列表中槽的位置摇零。一般地，我們把槽被占據(jù)的比例叫做負(fù)載因子桶蝎，** λ= 數(shù)據(jù)項(xiàng)個(gè)數(shù) / 散列表的大小驻仅。
???????當(dāng)然，當(dāng)散列函數(shù)計(jì)算出兩個(gè)甚至多個(gè)數(shù)據(jù)需要存儲(chǔ)在同一個(gè)槽中登渣，這表示散列函數(shù)不合適噪服，這種情況被稱為沖突。對(duì)于一組給定的數(shù)據(jù)項(xiàng)胜茧，如果一個(gè)散列函數(shù)可以將每一個(gè)數(shù)據(jù)項(xiàng)都映射到不同的槽中粘优，那么這樣的散列函數(shù)叫做完美散列函數(shù)。但是呻顽，如果給定的數(shù)據(jù)項(xiàng)是任意的敬飒，那么就沒有一種系統(tǒng)化的方法來(lái)構(gòu)造一個(gè)完美的散列函數(shù)。
4.2 排序
4.2.1 冒泡排序
python實(shí)現(xiàn)冒泡排序：(時(shí)間復(fù)雜度為O(n^2))
def bubbleSort1(alist):
for x_idx in range(len(alist) - 1, 0, -1):
for y_idx in range(x_idx):
# 如果前面的數(shù)據(jù)比后面大就往后排
if alist[y_idx] > alist[y_idx + 1]:
temp = alist[y_idx]
alist[y_idx] = alist[y_idx + 1]
alist[y_idx + 1] = temp
def bubbleSort2(alist):
passnum = len(alist) - 1
while passnum > 0:
for i in range(passnum):
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
passnum -= 1
testlist = [1, 4, 5, 23, 6, 435, 14, 61, 2354, 512, 4]
bubbleSort1(testlist)
print(testlist)
局限性：
???????因?yàn)槊芭菖判虮仨氁谧罱K位置找到之前不斷交換數(shù)據(jù)項(xiàng)芬位，所以它經(jīng)常被認(rèn)為是最低效的排序方法无拗。我們可以改良冒泡排序，使其在已知列表排好的情況下提前結(jié)束昧碉。這就是說(shuō)英染，如果一個(gè)列表只需要幾次遍歷就可排好，冒泡排序就占有優(yōu)勢(shì)：它可以在發(fā)現(xiàn)列表已排好時(shí)立刻結(jié)束被饿。這就是改良版冒泡排序四康。它通常被稱作“短路冒泡排序”。
def shortBubbleSort(alist):
exchanges = True
passnum = len(alist) - 1
while passnum > 0 and exchanges:
exchanges = False
for i in range(passnum):
if alist[i] > alist[i + 1]:
exchanges = True
alist[i], alist[i + 1] = alist[i + 1], alist[i]
passnum = passnum - 1
alist = [1, 45, 65, 3, 1, 3, 6, 7, 12, 457, 2, 45, 234]
shortBubbleSort(alist)
print(alist)
