可以看這個(gè)特別好的：《數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)》教學(xué)視頻目錄
1.單向鏈表
單鏈表節(jié)點(diǎn)一個(gè)類隙畜，單鏈表一個(gè)類闲孤，單鏈表這個(gè)類中的元素都是節(jié)點(diǎn)類的。
單鏈表的操作：
is_empty() 鏈表是否為空
取cur指向鏈表的首節(jié)點(diǎn)摹菠，判斷是不是Nonelength() 鏈表長(zhǎng)度
取cur指向鏈表的首節(jié)點(diǎn)眼耀，設(shè)置count用來(lái)計(jì)數(shù)宽气，當(dāng)前指向若不為None肠缨，則計(jì)數(shù)+1逆趋，移動(dòng)cur指向下一個(gè)節(jié)點(diǎn)。travel() 遍歷整個(gè)鏈表
思路同鏈表長(zhǎng)度晒奕，把計(jì)數(shù)的部分換成print-
first_add(item) 鏈表頭部添加元素
新添加的元素需要定義成節(jié)點(diǎn)類的一個(gè)實(shí)例闻书。新添加的元素就是頭節(jié)點(diǎn)，新添加節(jié)點(diǎn)的下一個(gè)指向原鏈表的頭節(jié)點(diǎn)脑慧。把鏈表的頭節(jié)點(diǎn)指向新添加的節(jié)點(diǎn)魄眉。
last_add(item) 鏈表尾部添加元素
新添加的元素需要定義成節(jié)點(diǎn)類的一個(gè)實(shí)例。
判斷當(dāng)前鏈表是不是為空闷袒，如果是空坑律，那這個(gè)鏈表的頭節(jié)點(diǎn)指向新添加的節(jié)點(diǎn)。
如果不是空囊骤，那就將cur指向頭節(jié)點(diǎn)脾歇，按照travel()的思路遍歷這個(gè)鏈表，一直走到最后一個(gè)節(jié)點(diǎn)淘捡，將最后一個(gè)節(jié)點(diǎn)的下一個(gè)元素設(shè)置為新添加的這個(gè)節(jié)點(diǎn)。注意判斷是否最后一個(gè)節(jié)點(diǎn)的條件池摧。-
insert(pos, item) 指定位置添加元素
新添加的元素需要定義成節(jié)點(diǎn)類的一個(gè)實(shí)例焦除。
判斷pos的值，如果pos<=0作彤，則相當(dāng)于在首部插入膘魄，調(diào)用首部插入的方法。
如果pos的值>鏈表長(zhǎng)度-1(注意這里pos的值是從0開(kāi)始的)竭讳，則相當(dāng)于尾部插入创葡，調(diào)用尾部插入的方法。
否則：定義pre指向當(dāng)前鏈表的頭節(jié)點(diǎn)绢慢，用一個(gè)count計(jì)算當(dāng)前指向的索引值灿渴，移動(dòng)cur直到走到pos-1的位置，將新節(jié)點(diǎn)的下一個(gè)元素指向原鏈表這個(gè)位置的下一個(gè)元素胰舆，原鏈表的下一個(gè)位置指向新節(jié)點(diǎn)骚露。見(jiàn)下圖
-
remove(item) 刪除節(jié)點(diǎn)
定義兩個(gè)指針，pre一開(kāi)始是None缚窿，cur 指向原鏈表的頭節(jié)點(diǎn)棘幸。如果刪除的是頭節(jié)點(diǎn)，那么把鏈表的頭節(jié)點(diǎn)指向原鏈表頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)倦零。如果不是頭節(jié)點(diǎn)误续，就將pre指向當(dāng)前cur的節(jié)點(diǎn)吨悍，cur的指向一個(gè)一個(gè)的往后挪，（這樣就相當(dāng)于pre在后蹋嵌，cur在前）直到cur指向的值就是我們要?jiǎng)h除的值育瓜，把pre的下一個(gè)節(jié)點(diǎn)指向cur的下一個(gè)節(jié)點(diǎn)。
search(item) 查找節(jié)點(diǎn)是否存在
思路同travel()
class Node(object):
def __init__(self,item):
self.item = item
self._next = None
class singleLinkList(object):
def __init__(self):
# 頭節(jié)點(diǎn)
self._head = None
def is_empty(self):
return self._head == None
def length(self):
# 首先要指向頭節(jié)點(diǎn)
cur = self._head
count = 0
while cur is not None:
count = count+1
cur = cur._next
return count
def travel(self):
if self.is_empty():
return
# 首先要指向頭節(jié)點(diǎn)
cur = self._head
while cur != None:
print(cur.item)
cur = cur._next
print("")
def first_add(self,elem):
# 把新添加的數(shù)定義到Node類里欣尼，這樣它就會(huì)有item和_next兩個(gè)屬性
p = Node(elem)
p._next = self._head
# 把鏈表的頭節(jié)點(diǎn)指向新添加的節(jié)點(diǎn)
self._head = p
def last_add(self,elem):
cur = self._head
p = Node(elem)
# 首先判斷這個(gè)鏈表是不是空的
if self.is_empty():
self._head = p
else:
cur = self._head
while cur._next != None:
cur = cur._next
cur._next = p
def insert(self,index,elem):
# 如果插入的地方在第一個(gè)位置之前爆雹，直接調(diào)用在首部插入的方法
if index<=0 :
self.first_add(elem)
# 如果插入的地方在最后一個(gè)位置之后，直接調(diào)用在尾部插入的方法
elif index>(self.length()-1):
self.last_add(elem)
else:
p = Node(elem)
count = 0
pre = self._head
while count<(index-1):
pre = pre._next
count = count+1
p._next = pre._next
pre._next = p
def remove(self,elem):
cur = self._head
pre = None
while cur is not None:
if cur.item == elem:
# 如果第一個(gè)就是要?jiǎng)h除的節(jié)點(diǎn)
if not pre:
self._head = cur._next
else:
pre._next = cur._next
break
else:
# 將刪除位置前一個(gè)節(jié)點(diǎn)的next指向刪除位置的后一個(gè)節(jié)點(diǎn)
pre = cur
cur = cur._next
def search(self,elem):
cur = self._head
index = 0
while cur is not None:
if cur.item == elem:
return index
else:
cur = cur._next
index = index+1
return index
if __name__ == "__main__":
ll = singleLinkList()
print("-------創(chuàng)建鏈表愕鼓，首部加1钙态，首部加2---------")
ll.first_add(1)
# print(ll.travel())
ll.first_add(2)
ll.travel()
print("-------尾部添加3---------")
ll.last_add(3)
ll.travel()
print("-------在索引為2的位置添加4---------")
ll.insert(2, 4)
print("length:",ll.length())
ll.travel()
print("-------查找鏈表中某一個(gè)數(shù)的索引---------")
index = ll.search(2)
print(index)
print("-------刪除鏈表中某一個(gè)數(shù)---------")
ll.remove(3)
# print "length:",ll.length()
ll.travel()
2.循環(huán)單鏈表
-
首部添加元素
首先判斷這個(gè)鏈表是不是空，如果是空菇晃，把頭指針指向新添加的這個(gè)p節(jié)點(diǎn)册倒，并且p節(jié)點(diǎn)的下一節(jié)點(diǎn)指向頭節(jié)點(diǎn)。（因?yàn)槭茄h(huán)的）
如果不是空磺送，那么先把p節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向頭節(jié)點(diǎn)驻子，然后往后走，找到最后一個(gè)節(jié)點(diǎn)估灿，把原鏈表的最后一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向新加入的p節(jié)點(diǎn)崇呵，并且把頭指針指向這個(gè)p節(jié)點(diǎn)（因?yàn)槭鞘撞考尤耄?/p> - 尾部添加元素
首先判斷原鏈表是不是空的，如果是空的馅袁，就按照上面的域慷，把頭指針(self._head)指向新添加的這個(gè)p節(jié)點(diǎn)，并且p節(jié)點(diǎn)的下一節(jié)點(diǎn)指向頭節(jié)點(diǎn)汗销。
如果不是空犹褒，就找到原鏈表的最后一個(gè)節(jié)點(diǎn)，將最后一個(gè)節(jié)點(diǎn)的下一節(jié)點(diǎn)指向p節(jié)點(diǎn)弛针，然后p節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向頭節(jié)點(diǎn)叠骑，頭指針(self._head)沒(méi)變。 - remove方法還需要好好看看削茁。
class Node(object):
def __init__(self,item):
self.item = item
self._next = None
class circularLinkList(object):
def __init__(self):
# 頭節(jié)點(diǎn)
self._head = None
def is_empty(self):
return self._head == None
def length(self):
# 首先要指向頭節(jié)點(diǎn)
cur = self._head
count = 0
while cur is not None:
count = count+1
cur = cur._next
return count
def travel(self):
if self.is_empty():
return
# 首先要指向頭節(jié)點(diǎn)
cur = self._head
while cur._next != self._head:
print(cur.item)
cur = cur._next
print(cur.item)
print("")
def first_add(self,elem):
# 把新添加的數(shù)定義到Node類里宙枷，這樣它就會(huì)有item和_next兩個(gè)屬性
p = Node(elem)
if self.is_empty():
self._head = p
p._next = self._head
else:
# 首先將新加入的這個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向首節(jié)點(diǎn)
p._next = self._head
# 然后將原鏈表的尾節(jié)點(diǎn)指向這個(gè)新加入的節(jié)點(diǎn)
cur = self._head
while cur._next != self._head:
cur = cur._next
cur._next = p
self._head = p
def last_add(self,elem):
p = Node(elem)
# 首先判斷這個(gè)鏈表是不是空的
if self.is_empty():
self._head = p
p._next = self._head
else:
# 直接走到最后的節(jié)點(diǎn)
cur = self._head
while cur._next != self._head:
cur = cur._next
cur._next = p
p._next = self._head
def insert(self,index,elem):
# 如果插入的地方在第一個(gè)位置之前，直接調(diào)用在首部插入的方法
if index<=0 :
self.first_add(elem)
# 如果插入的地方在最后一個(gè)位置之后茧跋，直接調(diào)用在尾部插入的方法
elif index>(self.length()-1):
self.last_add(elem)
else:
p = Node(elem)
count = 0
pre = self._head
while count<(index-1):
pre = pre._next
count = count+1
p._next = pre._next
pre._next = p
def remove(self,elem):
# 如果原鏈表為空
if self.is_empty():
return
cur = self._head
pre = None
# 如果鏈表的第一個(gè)元素就是要?jiǎng)h除的元素
if cur.item == elem:
# 如果鏈表多于一個(gè)節(jié)點(diǎn)朦拖，就找到最后一個(gè)節(jié)點(diǎn)
if cur._next != self._head:
while cur._next != self._head:
cur = cur._next
cur._next = self._head._next
self._head = self._head._next
else:
# 如果鏈表只有一個(gè)元素，就直接置空
self._head = None
else:
pre = self._head
while cur._next != self._head:
# 如果找到了要找的元素
if cur.item == elem:
pre._next = cur._next
return
else:
pre = cur
cur = cur._next
# cur指向了尾節(jié)點(diǎn)
if cur.item == elem:
pre._next = self._head
def search(self,elem):
if self.is_empty():
return False
cur = self._head
index = 0
while cur._next != self._head:
if cur.item == elem:
return index
else:
cur = cur._next
index = index+1
if cur.item == elem:
return index
else:
return False
if __name__ == "__main__":
ll = circularLinkList()
# print(ll.length())
ll.travel()
print("--------首部添加----------")
ll.first_add(2)
ll.first_add(1)
ll.first_add(99)
ll.travel()
print("--------尾部添加----------")
ll.last_add(6)
ll.travel()
print("--------尾部添加----------")
ll.last_add(5)
ll.travel()
print("--------移除元素----------")
# ll.remove(5)
# ll.travel()
print("--------查找元素----------")
print(ll.search(6))
3.棧
棧是一種特殊的線性表厌衔，僅能在線性表的一端操作璧帝，棧頂允許操作，棧底不允許操作富寿。
棧的特性：后進(jìn)先出
class Stack(object):
def __init__(self):
self.items = []
def is_empty(self):
# 判斷棧是否為空
return self.items == []
def push(self,elem):
# 添加元素到棧
self.items.append(elem)
def pop(self):
# 彈出元素
return self.items.pop()
def peek(self):
# 返回棧頂?shù)脑? return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def travel(self):
for i in range(self.size()):
print(self.items[i],end=" ")
if __name__ == '__main__':
stack = Stack()
print(stack.travel())
print("======判斷棧是否為空==========")
print(stack.is_empty())
print("======棧頂加入元素==========")
stack.push(2)
stack.push(3)
stack.push(12)
stack.push(4)
print(stack.travel())
print("棧的長(zhǎng)度為：", stack.size())
print("======判斷棧是否為空==========")
print(stack.is_empty())
print("======彈出棧頂元素==========")
print(stack.pop())
print("======返回棧頂元素==========")
print(stack.peek())
print("棧的長(zhǎng)度為：",stack.size())
4.隊(duì)列
隊(duì)列是一種特殊的線性表睬隶，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作锣夹，而在表的后端（rear）進(jìn)行插入操作。
特點(diǎn)：先進(jìn)先出
class Queue(object):
def __init__(self):
self.items =[]
def is_empty(self):
return self.items == []
def enqueue(self,elem):
# 隊(duì)列添加元素
self.items.insert(0,elem)
def dequeue(self):
# 從隊(duì)列頭部刪除一個(gè)元素
return self.items.pop()
def size(self):
return len(self.items)
if __name__ == '__main__':
queue = Queue()
print("======判斷隊(duì)列是否為空==========")
print(queue.is_empty())
print("======隊(duì)列加入元素==========")
queue.enqueue(2)
queue.enqueue("hello")
queue.enqueue("end")
print("隊(duì)列的長(zhǎng)度為：", queue.size())
print("======判斷隊(duì)列是否為空==========")
print(queue.is_empty())
print("======返回隊(duì)列頭部元素==========")
print(queue.dequeue())
print("隊(duì)列的長(zhǎng)度為：",queue.size())
雙端隊(duì)列
特點(diǎn)：雙端隊(duì)列可以在隊(duì)列任意一端入隊(duì)和出隊(duì)。
class DoubleQueue(object):
"""
Deque() 創(chuàng)建一個(gè)空的雙端隊(duì)列
add_front(item) 從隊(duì)頭加入一個(gè)item元素
add_rear(item) 從隊(duì)尾加入一個(gè)item元素
remove_front() 從隊(duì)頭刪除一個(gè)item元素
remove_rear() 從隊(duì)尾刪除一個(gè)item元素
is_empty() 判斷雙端隊(duì)列是否為空
size() 返回隊(duì)列的大小
"""
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def add_front(self,elem):
# 從隊(duì)頭加入一個(gè)元素
self.items.insert(0,elem)
def add_rear(self,elem):
# 隊(duì)尾加入一個(gè)元素
self.items.append(elem)
def remove_front(self):
# 隊(duì)頭刪除一個(gè)元素
return self.items.pop(0)
def remove_rear(self):
# 隊(duì)尾刪除一個(gè)元素
return self.items.pop()
def size(self):
return len(self.items)
def travel(self):
for i in range(self.size()):
print(self.items[i],end=" ")
if __name__ == '__main__':
deque = DoubleQueue()
print("======判斷雙端隊(duì)列是否為空==========")
print(deque.is_empty())
deque.add_front(1)
deque.add_front(2)
deque.add_rear(3)
deque.add_rear(4)
print("======雙端隊(duì)列的值為:==========")
deque.travel()
print("雙端隊(duì)列的長(zhǎng)度為:",deque.size())
print("======隊(duì)頭刪除的元素==========")
print(deque.remove_front())
print("======隊(duì)尾刪除的元素==========")
print(deque.remove_rear())
print("雙端隊(duì)列的長(zhǎng)度為:", deque.size())
4.樹(shù)
二叉樹(shù)
對(duì)于任意一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)為N0咧虎，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2骚灸，則N0=N2+1;
證明需要知道：二叉樹(shù)(非空)的結(jié)點(diǎn)數(shù)等于邊數(shù)+1(可以理解為淑趾，除了根節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一條邊)，可以設(shè)度數(shù)為0的節(jié)點(diǎn)為N0，度數(shù)為1的節(jié)點(diǎn)N1戳气，度數(shù)為2的節(jié)點(diǎn)N2，有N0+N1+N2(節(jié)點(diǎn)數(shù))= 1+N1+2N2(邊數(shù))巧鸭，度數(shù)為1的節(jié)點(diǎn)對(duì)對(duì)應(yīng)一個(gè)邊瓶您，度數(shù)為2的節(jié)點(diǎn)對(duì)應(yīng)兩個(gè)邊。
-
滿二叉樹(shù)：一棵深度為k且有2的k次方減1個(gè)結(jié)點(diǎn)的二叉樹(shù)是滿二叉樹(shù)纲仍。除葉子結(jié)點(diǎn)外的所有結(jié)點(diǎn)均有兩個(gè)子結(jié)點(diǎn)呀袱。節(jié)點(diǎn)數(shù)達(dá)到最大值。所有葉子結(jié)點(diǎn)必須在同一層上郑叠。
-
完全二叉樹(shù)：若設(shè)二叉樹(shù)的深度為h夜赵，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)乡革，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊油吭，這就是完全二叉樹(shù)。
二者的關(guān)系：滿二叉樹(shù)肯定是完全二叉樹(shù)署拟，完全二叉樹(shù)不一定是滿二叉樹(shù)。
- 平衡二叉樹(shù)（AVL樹(shù)）：當(dāng)且僅當(dāng)任何節(jié)點(diǎn)的兩棵子樹(shù)的高度差不大于1的二叉樹(shù)歌豺；
- 排序二叉樹(shù)（二叉查找樹(shù)（英語(yǔ)：Binary Search Tree）推穷，也稱二叉搜索樹(shù)、有序二叉樹(shù)）类咧；
樹(shù)的前序遍歷：中左右
中序遍歷：左中右
后續(xù)遍歷：左右中
5. 圖 G=(V,E)
相關(guān)概念
圖的組成：頂點(diǎn)V和邊E
分類：有向圖和無(wú)向圖
頂點(diǎn)的度：對(duì)于無(wú)向圖來(lái)說(shuō)馒铃，一個(gè)頂點(diǎn)的度就是連接該頂點(diǎn)的邊的數(shù)量，記做D(V)痕惋；對(duì)于有向圖來(lái)說(shuō)区宇，分為入度ID(V)（以該頂點(diǎn)為端點(diǎn)的入邊數(shù)量）和出度OD(V)（以該頂點(diǎn)為端點(diǎn)的出邊數(shù)量），D(V)=ID(V)+OD(V)
鄰接頂點(diǎn)：對(duì)于無(wú)向圖來(lái)說(shuō)值戳，就是一條邊的兩個(gè)頂點(diǎn)议谷；對(duì)于有向圖來(lái)說(shuō)，兩個(gè)頂點(diǎn)分別稱為起始頂點(diǎn)（入邊鄰接頂點(diǎn)）和結(jié)束頂點(diǎn)（出邊鄰接頂點(diǎn)）
無(wú)向完全圖：M個(gè)頂點(diǎn)的無(wú)向完全圖總邊數(shù)為M(M-1)/2
有向完全圖：N個(gè)頂點(diǎn)的有向完全圖堕虹，總邊數(shù)為N(N-1)
有向無(wú)環(huán)圖（DAG圖）：一個(gè)有向圖從一個(gè)頂點(diǎn)出發(fā)經(jīng)過(guò)若干條邊無(wú)法回到該頂點(diǎn)卧晓。
網(wǎng)（即有權(quán)圖）
圖的存儲(chǔ)結(jié)構(gòu)
圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣表示法芬首、鄰接表表示法
1??鄰接矩陣表示法：就是用兩個(gè)數(shù)組表示圖。缺點(diǎn)是n個(gè)頂點(diǎn)的圖需要n*n個(gè)存儲(chǔ)空間逼裆，當(dāng)圖為稀疏圖時(shí)會(huì)造成空間浪費(fèi)郁稍。
頂點(diǎn)表記錄頂點(diǎn)信息，鄰接矩陣表示頂點(diǎn)之間的關(guān)系胜宇。
有向圖鄰接矩陣中第i行表示以結(jié)點(diǎn)vi為尾的灰（即出度邊[發(fā)出的弧]），第j列表示的是以結(jié)點(diǎn)vj為頭的煌┯洹（即入度邊）财破，頂點(diǎn)的出度=第i行元素之和，頂點(diǎn)的入度=第j列元素之和
2??鄰接表表示法：（多重鏈表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）
頭結(jié)點(diǎn)：一維數(shù)組仅财，其中有兩個(gè)元素狈究，第一個(gè)元素是頂點(diǎn)的數(shù)據(jù)元素本身，第二個(gè)元素是指針盏求，指向邊結(jié)點(diǎn)的地址抖锥。
表結(jié)點(diǎn)：第一個(gè)元素表示鄰接的頂點(diǎn)是頂點(diǎn)表中的哪個(gè)元素，第二個(gè)指針指向下一個(gè)邊碎罚。
對(duì)于一個(gè)頂點(diǎn)來(lái)說(shuō)磅废，有幾個(gè)邊就記錄幾個(gè)邊結(jié)點(diǎn)
如果是網(wǎng)，可以在表結(jié)點(diǎn)中增加一個(gè)域表示權(quán)值荆烈。
特點(diǎn)：
鄰接表不唯一拯勉；若無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則鄰接表需要n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)憔购，適合存儲(chǔ)稀疏圖宫峦；有向圖中有n個(gè)頂點(diǎn)e條邊，則鄰接表需要n個(gè)頭結(jié)點(diǎn)和e個(gè)表結(jié)點(diǎn)
怎么看度玫鸟？有幾個(gè)表結(jié)點(diǎn)就是有幾個(gè)度导绷。
3.排序
冒泡排序（O(n^2)）
思路：比較前后兩個(gè)數(shù)的大小，從前到后比較到最后屎飘，這樣第一次冒泡完最后一個(gè)數(shù)是整個(gè)里面最大的數(shù)妥曲，然后進(jìn)行第二次冒泡...假設(shè)我們要排序的有m個(gè)數(shù)，那么就需要m-1次冒泡钦购。
def BubbleSort(myList):
length = len(myList)
for i in range(length-1):
#注意這個(gè)地方檐盟，因?yàn)檫€有一個(gè)j+1,所以j的取值是length-i-1
for j in range(length-i-1):
if myList[j]>myList[j+1]:
myList[j],myList[j+1] = myList[j+1],myList[j]
print(myList)
BubbleSort([49,38,65,97,76,13,27])
選擇排序（O(n^2)）
思路：首先在未排序序列中找到最小（大）元素押桃，存放到排序序列的起始位置葵萎，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素陌宿，然后放到已排序序列的末尾锡足。以此類推，直到所有元素均排序完畢壳坪。
注：選擇排序每一趟只交換一個(gè)數(shù)２暗谩！所以在每一趟比較的時(shí)候記錄下來(lái)最小的數(shù)的索引值爽蝴，在未排序序列都遍歷過(guò)一邊之后沐批，把最小的值和第一個(gè)為止的進(jìn)行交換。
def Selection_sort(myList):
length = len(myList)
# 總共需要length-1次蝎亚，因?yàn)榈趌ength次前面的都定了
for i in range(length-1):
min_index = i
for j in range(i,length):
if myList[j]<myList[min_index]:
min_index = j
if min_index != i:
myList[i],myList[min_index]=myList[min_index],myList[i]
print(myList)
Selection_sort([49,38,65,97,76,13,27])
插入排序(O(n^2))
思路：未排序數(shù)據(jù)九孩，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入发框。
def insert_sort(myList):
length = len(myList)
for i in range(1,length):
for j in range(i,0,-1):
if myList[j]<myList[j-1]:
myList[j],myList[j-1] = myList[j-1],myList[j]
print(myList)
def insert_sort(myList):
length = len(myList)
for i in range(1,length):
if myList[i]<myList[i-1]:
index = i
temp = myList[i]
while index>0 and myList[index-1]>temp:
myList[index]=myList[index-1]
index = index-1
myList[index] = temp
insert_sort([49,38,65,97,76,13,27,49])
快速排序(O(nlogn))
思想：
算法-快速排序-python3實(shí)現(xiàn)
講的很好的視頻
def QuickSort(myList,start,end):
i,j = start,end
base = myList[i]
while i<j:
while i<j and myList[j]>=base:
j = j-1
myList[i]=myList[j]
while i<j and myList[i]<=base:
i=i+1
myList[j]=myList[i]
myList[i] = base
QuickSort(myList,start,i-1)
QuickSort(myList,j+1,end)
myList = [49,38,65,97,76,13,27,49]
print("Quick Sort: ")
QuickSort(myList,0,len(myList)-1)
print(myList)
快速排序2:
def quick_sort(self,lst):
if not lst:
return []
pivot = lst[0]
left = self.quick_sort([x for x in lst[1: ] if x < pivot])
right = self.quick_sort([x for x in lst[1: ] if x >= pivot])
return left + [pivot] + right
歸并排序：
實(shí)質(zhì)其實(shí)就是合并兩個(gè)有序的列表
def merge_sort(collection):
if len(collection)<=1:
return collection
mid = len(collection) // 2
return merge(merge_sort(collection[:mid]), merge_sort(collection[mid:]))
def merge(left,right):
result=[]
while left and right:
result.append(left.pop(0) if left[0]<=right[0] else right.pop(0))
return result+left+right
print(merge_sort([2,-1,0,3,1,9]))
堆排序：
1??Python實(shí)現(xiàn)：
堆排序的Python實(shí)現(xiàn)(附詳細(xì)過(guò)程圖和講解)
主要的思想是先構(gòu)建一個(gè)大根堆躺彬，然后讓大根堆的頂點(diǎn)與堆右下角的元素交換，再構(gòu)建成大根堆梅惯。
堆宪拥，其實(shí)就是一個(gè)完全二叉樹(shù)，特點(diǎn)是根節(jié)點(diǎn)的值最大（大根堆）或者最邢臣酢（小根堆）
2??Python調(diào)用heaq庫(kù) （參考這篇文章Python標(biāo)準(zhǔn)庫(kù)模塊之heapq）
# 使用heaq庫(kù)構(gòu)建堆
import heapq
nums = [2, 3, 5, 1, 54, 23, 132]
heap = []
for num in nums:
heapq.heappush(heap, num)
#heapq.heappop() 函數(shù)彈出堆中最小值
print([heapq.heappop(heap) for _ in range(len(nums))])
#獲取堆中的最大或最小的范圍值
print(heapq.nlargest(3, nums))
print(heapq.nsmallest(3, nums))
4.常見(jiàn)算法
窮舉法
貪心法：典型例子是最大連續(xù)子數(shù)組和（不太確定下面這個(gè)是不是用貪心法做的）
class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
if not array:
return 0
cur_sum = 0
max_sum = array[0]
for i in range(len(array)):
if cur_sum <= 0:
cur_sum = array[i]
else:
cur_sum += array[i]
if cur_sum > max_sum:
max_sum = cur_sum
return max_sum
分治法 ：典型例子有快排
回溯法：例子有那個(gè)左上到右下的棋盤
動(dòng)態(tài)規(guī)劃 ：
