常用排序 名稱 複雜度 說明 備註 冒泡排序Bubble Sort O(N*N) 將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮 插入排序 Insertion sort O(N*N) 逐一取出元素，在已經排序的元素序列中從後向前掃描，放到適當的位置 起初，已經排序的元素序列為 ...
常用排序
|
名稱 |
複雜度 |
說明 |
備註 |
|
冒泡排序 |
O(N*N) |
將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮 |
|
|
插入排序 Insertion sort |
O(N*N) |
逐一取出元素，在已經排序的元素序列中從後向前掃描，放到適當的位置 |
起初，已經排序的元素序列為空 |
|
選擇排序 |
O(N*N) |
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小元素，然後放到排序序列末尾。以此遞歸。 |
|
|
快速排序 Quick Sort |
O(n *log2(n)) |
先選擇中間值，然後把比它小的放在左邊，大的放在右邊（具體的實現是從兩邊找，找到一對後交換）。然後對兩邊分別使用這個過程（遞歸）。 |
|
|
堆排序 HeapSort |
O(n *log2(n)) |
利用堆（heaps）這種數據結構來構造的一種排序演算法。堆是一個近似完全二叉樹結構，並同時滿足堆屬性：即子節點的鍵值或索引總是小於（或者大於）它的父節點。 |
近似完全二叉樹 |
|
希爾排序 SHELL |
O(n1+￡) 0<￡<1 |
選擇一個步長(Step) ,然後按間隔為步長的單元進行排序.遞歸,步長逐漸變小,直至為1. |
|
|
箱排序 |
O(n) |
設置若幹個箱子，把關鍵字等於 k 的記錄全都裝入到第k 個箱子里 ( 分配 ) ，然後按序號依次將各非空的箱子首尾連接起來 ( 收集 ) 。 |
分配排序的一種：通過" 分配 " 和 " 收集 " 過程來實現排序。 |
冒泡排序（Bubble Sort）
冒泡排序（Bubble Sort），是一種電腦科學領域的較簡單的排序演算法。 它重覆地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重覆地進行直到沒有再需要交換，也就是說該數列已經排序完成。 這個演算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端，故名。
1 data_set = [ 9,1,22,31,45,3,6,2,11 ]
2
3 loop_count = 0
4 for j in range(len(data_set)):
5 for i in range(len(data_set) - j- 1):
6 # -1 是因為每次比對的都 是i 與i +1,不減1的話,最後一次對比會超出list 獲取範圍,
7 # -j是因為,每一次大loop就代表排序好了一個最大值,放在了列表最後面,
8 # 下次loop就不用再運算已經排序好了的值 了
9 if data_set[i] > data_set[i+1]: #switch
10 tmp = data_set[i]
11 data_set[i] = data_set[i+1]
12 data_set[i+1] = tmp
13 loop_count +=1
14 print(data_set)
15 print(data_set)
16 print("loop times", loop_count)
View Code
選擇排序
The algorithm works by selecting the smallest unsorted item and then swapping it with the item in the next position to be filled.
The selection sort works as follows: you look through the entire array for the smallest element, once you find it you swap it (the smallest element) with the first element of the array. Then you look for the smallest element in the remaining array (an array without the first element) and swap it with the second element. Then you look for the smallest element in the remaining array (an array without first and second elements) and swap it with the third element, and so on. Here is an example,
1 data_set = [ 9,1,22,31,45,3,6,2,11 ]
2
3 smallest_num_index = 0 #初始列表最小值,預設為第一個
4
5 loop_count = 0
6 for j in range(len(data_set)):
7 for i in range(j,len(data_set)):
8 if data_set[i] < data_set[smallest_num_index]:
9 #當前值 比之前選出來的最小值 還要小,那就把它換成最小值
10 smallest_num_index = i
11 loop_count +=1
12 else:
13 print("smallest num is ",data_set[smallest_num_index])
14 tmp = data_set[smallest_num_index]
15 data_set[smallest_num_index] = data_set[j]
16 data_set[j] = tmp
17
18 print(data_set)
19 print("loop times", loop_count)
View Code
The worst-case runtime complexity is O(n2).
插入排序(Insertion Sort)
插入排序(Insertion Sort)的基本思想是：將列表分為2部分，左邊為排序好的部分，右邊為未排序的部分，迴圈整個列表，每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子序列中的適當位置，直到全部記錄插入完成為止。
插入排序非常類似於整撲克牌。
在開始摸牌時，左手是空的，牌面朝下放在桌上。接著，一次從桌上摸起一張牌，並將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置，要將它與手中已有的牌從右到左地進行比較。無論什麼時候，左手中的牌都是排好序的。
也許你沒有意識到，但其實你的思考過程是這樣的：現在抓到一張7，把它和手裡的牌從右到左依次比較，7比10小，應該再往左插，7比5大，好，就插這裡。為什麼比較了10和5就可以確定7的位置？為什麼不用再比較左邊的4和2呢？因為這裡有一個重要的前提：手裡的牌已經是排好序的。現在我插了7之後，手裡的牌仍然是排好序的，下次再抓到的牌還可以用這個方法插入。編程對一個數組進行插入排序也是同樣道理，但和插入撲克牌有一點不同，不可能在兩個相鄰的存儲單元之間再插入一個單元，因此要將插入點之後的數據依次往後移動一個單元。
1 source = [92, 77, 67, 8, 6, 84, 55, 85, 43, 67]
2
3
4 for index in range(1,len(source)):
5 current_val = source[index] #先記下來每次大迴圈走到的第幾個元素的值
6 position = index
7
8 while position > 0 and source[position-1] > current_val: #當前元素的左邊的緊靠的元素比它大,要把左邊的元素一個一個的往右移一位,給當前這個值插入到左邊挪一個位置出來
9 source[position] = source[position-1] #把左邊的一個元素往右移一位
10 position -= 1 #只一次左移只能把當前元素一個位置 ,還得繼續左移只到此元素放到排序好的列表的適當位置 為止
11
12 source[position] = current_val #已經找到了左邊排序好的列表裡不小於current_val的元素的位置,把current_val放在這裡
13 print(source)
View Code
結果：
[77, 92, 67, 8, 6, 84, 55, 85, 43, 67]
[67, 77, 92, 8, 6, 84, 55, 85, 43, 67]
[8, 67, 77, 92, 6, 84, 55, 85, 43, 67]
[6, 8, 67, 77, 92, 84, 55, 85, 43, 67]
[6, 8, 67, 77, 84, 92, 55, 85, 43, 67]
[6, 8, 55, 67, 77, 84, 92, 85, 43, 67]
[6, 8, 55, 67, 77, 84, 85, 92, 43, 67]
[6, 8, 43, 55, 67, 77, 84, 85, 92, 67]
[6, 8, 43, 55, 67, 67, 77, 84, 85, 92]
#更容易理解的版本
1 data_set = [ 9,1,22,9,31,-5,45,3,6,2,11 ]
2 for i in range(len(data_set)):
3 #position = i
4 while i > 0 and data_set[i] < data_set[i-1]:# 右邊小於左邊相鄰的值
5 tmp = data_set[i]
6 data_set[i] = data_set[i-1]
7 data_set[i-1] = tmp
8 i -= 1
9 # position = i
10 # while position > 0 and data_set[position] < data_set[position-1]:# 右邊小於左邊相鄰的值
11 # tmp = data_set[position]
12 # data_set[position] = data_set[position-1]
13 # data_set[position-1] = tmp
14 # position -= 1
15
16 插入排序
插入排序
快速排序（quick sort）
設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。值得註意的是，快速排序不是一種穩定的排序演算法，也就是說，多個相同的值的相對位置也許會在演算法結束時產生變動
註：在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生改變，則稱這種排序方法是不穩定的。
要註意的是，排序演算法的穩定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得演算法不滿足穩定性要求，則該排序演算法就是不穩定的。
排序演示
示例
假設用戶輸入瞭如下數組：| 下標 | 0 | 1 | 2 | 3 | 4 | 5 |
| 數據 | 6 | 2 | 7 | 3 | 8 | 9 |
| 下標 | 0 | 1 | 2 | 3 | 4 | 5 |
| 數據 | 3 | 2 | 7 | 6 | 8 | 9 |
| 下標 | 0 | 1 | 2 | 3 | 4 | 5 |
| 數據 | 3 | 2 | 6 | 7 | 8 | 9 |
| 下標 | 0 | 1 | 2 | 3 | 4 | 5 |
| 數據 | 3 | 2 | 6 | 7 | 8 | 9 |
1 def quick_sort(array,left,right):
2 '''
3 :param array:
4 :param left: 列表的第一個索引
5 :param right: 列表最後一個元素的索引
6 :return:
7 '''
8 if left >=right:
9 return
10 low = left
11 high = right
12 key = array[low] #第一個值
13
14 while low < high:#只要左右未遇見
15 while low < high and array[high] > key: #找到列表右邊比key小的值 為止
16 high -= 1
17 #此時直接 把key(array[low]) 跟 比它大的array[high]進行交換
18 array[low] = array[high]
19 array[high] = key
20
21
22 while low < high and array[low] <= key : #找到key左邊比key大的值 為止
23 low += 1
24 #找到了左邊比k大的值 ,把array[high](此時應該剛存成了key) 跟這個比key大的array[low]進行調換
25 array[high] = array[low]
26 array[low] = key
27
28 quick_sort(array,left,low-1) #最後用同樣的方式對分出來的左邊的小組進行同上的做法
29 quick_sort(array,low+1, right)#用同樣的方式對分出來的右邊的小組進行同上的做法
30
31
32
33 if __name__ == '__main__':
34
35 array = [96,14,10,9,6,99,16,5,1,3,2,4,1,13,26,18,2,45,34,23,1,7,3,22,19,2]
36 #array = [8,4,1, 14, 6, 2, 3, 9,5, 13, 7,1, 8,10, 12]
37 print("before sort:", array)
38 quick_sort(array,0,len(array)-1)
39
40 print("-------final -------")
41 print(array)
View Code
二叉樹
樹的特征和定義
樹是一種重要的非線性數據結構，直觀地看，它是數據元素（在樹中稱為結點）按分支關係組織起來的結構，很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在電腦領域中也得到廣泛應用，如在編譯源程式時，可用樹表示源程式的語法結構。又如在資料庫系統中，樹型結構也是信息的重要組織形式之一。一切具有層次關係的問題都可用樹來描述。樹(Tree)是元素的集合。我們先以比較直觀的方式介紹樹。下麵的數據結構是一個樹：
樹有多個節點(node)，用以儲存元素。某些節點之間存在一定的關係，用連線表示，連線稱為邊(edge)。邊的上端節點稱為父節點，下端稱為子節點。樹像是一個不斷分叉的樹根。
每個節點可以有多個子節點(children)，而該節點是相應子節點的父節點(parent)。比如說，3,5是6的子節點，6是3,5的父節點；1,8,7是3的子節點, 3是1,8,7的父節點。樹有一個沒有父節點的節點，稱為根節點(root)，如圖中的6。沒有子節點的節點稱為葉節點(leaf)，比如圖中的1,8,9,5節點。從圖中還可以看到，上面的樹總共有4個層次，6位於第一層，9位於第四層。樹中節點的最大層次被稱為深度。也就是說，該樹的深度(depth)為4。
如果我們從節點3開始向下看，而忽略其它部分。那麼我們看到的是一個以節點3為根節點的樹：
三角形代表一棵樹
再進一步，如果我們定義孤立的一個節點也是一棵樹的話，原來的樹就可以表示為根節點和子樹(subtree)的關係:
上述觀察實際上給了我們一種嚴格的定義樹的方法：
1. 樹是元素的集合。
2. 該集合可以為空。這時樹中沒有元素，我們稱樹為空樹 (empty tree)。
3. 如果該集合不為空，那麼該集合有一個根節點，以及0個或者多個子樹。根節點與它的子樹的根節點用一個邊(edge)相連。
上面的第三點是以遞歸的方式來定義樹，也就是在定義樹的過程中使用了樹自身(子樹)。由於樹的遞歸特征，許多樹相關的操作也可以方便的使用遞歸實現。我們將在後面看到。
樹的實現
樹的示意圖已經給出了樹的一種記憶體實現方式: 每個節點儲存元素和多個指向子節點的指針。然而，子節點數目是不確定的。一個父節點可能有大量的子節點，而另一個父節點可能只有一個子節點，而樹的增刪節點操作會讓子節點的數目發生進一步的變化。這種不確定性就可能帶來大量的記憶體相關操作，並且容易造成記憶體的浪費。
一種經典的實現方式如下:
樹的記憶體實現
擁有同一父節點的兩個節點互為兄弟節點(sibling)。上圖的實現方式中，每個節點包含有一個指針指向第一個子節點，並有另一個指針指向它的下一個兄弟節點。這樣，我們就可以用統一的、確定的結構來表示每個節點。
電腦的文件系統是樹的結構。在UNIX的文件系統中，每個文件(文件夾同樣是一種文件)，都可以看做是一個節點。非文件夾的文件被儲存在葉節點。文件夾中有指向父節點和子節點的指針(在UNIX中，文件夾還包含一個指向自身的指針，這與我們上面見到的樹有所區別)。在git中，也有類似的樹狀結構，用以表達整個文件系統的版本變化 。
二叉樹
二叉樹是由n（n≥0）個結點組成的有限集合、每個結點最多有兩個子樹的有序樹。它或者是空集，或者是由一個根和稱為左、右子樹的兩個不相交的二叉樹組成。
特點：
（1）二叉樹是有序樹，即使只有一個子樹，也必須區分左、右子樹；
（2）二叉樹的每個結點的度不能大於2，只能取0、1、2三者之一；
（3）二叉樹中所有結點的形態有5種：空結點、無左右子樹的結點、只有左子樹的結點、只有右子樹的結點和具有左右子樹的結點。
二叉樹(binary)是一種特殊的樹。二叉樹的每個節點最多只能有2個子節點：
二叉樹
由於二叉樹的子節點數目確定，所以可以直接採用上圖方式在記憶體中實現。每個節點有一個左子節點(left children)和右子節點(right children)。左子節點是左子樹的根節點，右子節點是右子樹的根節點。
如果我們給二叉樹加一個額外的條件，就可以得到一種被稱作二叉搜索樹(binary search tree)的特殊二叉樹。二叉搜索樹要求：每個節點都不比它左子樹的任意元素小，而且不比它的右子樹的任意元素大。
(如果我們假設樹中沒有重覆的元素，那麼上述要求可以寫成：每個節點比它左子樹的任意節點大，而且比它右子樹的任意節點小)
二叉搜索樹，註意樹中元素的大小
二叉搜索樹可以方便的實現搜索演算法。在搜索元素x的時候，我們可以將x和根節點比較:
1. 如果x等於根節點，那麼找到x，停止搜索 (終止條件)
2. 如果x小於根節點，那麼搜索左子樹
3. 如果x大於根節點，那麼搜索右子樹
二叉搜索樹所需要進行的操作次數最多與樹的深度相等。n個節點的二叉搜索樹的深度最多為n，最少為log(n)。
二叉樹的遍歷
遍歷即將樹的所有結點訪問且僅訪問一次。按照根節點位置的不同分為前序遍歷，中序遍歷，後序遍歷。
前序遍歷：根節點->左子樹->右子樹
中序遍歷：左子樹->根節點->右子樹
後序遍歷：左子樹->右子樹->根節點
例如：求下麵樹的三種遍歷
前序遍歷：abdefgc
中序遍歷：debgfac
後序遍歷：edgfbca
二叉樹的類型
(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子節點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。 (2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。 (3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL演算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹如何判斷一棵樹是完全二叉樹？按照定義，
教材上的說法：一個深度為k，節點個數為 2^k - 1 的二叉樹為滿二叉樹。這個概念很好理解，
就是一棵樹，深度為k，並且沒有空位。
首先對滿二叉樹按照廣度優先遍歷（從左到右）的順序進行編號。
一顆深度為k二叉樹，有n個節點，然後，也對這棵樹進行編號，如果所有的編號都和滿二叉樹對應，那麼這棵樹是完全二叉樹。
二叉樹遍歷實現
1 class TreeNode(object):
2 def __init__(self,data=0,left=0,right=0):
3 self.data = data
4 self.left = left
5 self.right = right
6
7 class BTree(object):
8 def __init__(self,root=0):
9 self.root = root
10
11
12 def preOrder(self,treenode):
13 if treenode is 0:
14 return
15 print(treenode.data)
16 self.preOrder(treenode.left)
17 self.preOrder(treenode.right)
18 def inOrder(self,treenode):
19 if treenode is 0:
20 return
21 self.inOrder(treenode.left)
22 print(treenode.data)
23 self.inOrder(treenode.right)
24
25 def postOrder(self,treenode):
26 if treenode is 0:
27 return
28 self.postOrder(treenode.left)
29 self.postOrder(treenode.right)
30 print(treenode.data)
31 if __name__ == '__main__':
32 n1 = TreeNode(data=1)
33 n2 = TreeNode(2,n1,0)
34 n3 = TreeNode(3)
35 n4 = TreeNode(4)
36 n5 = TreeNode(5,n3,n4)
37 n6 = TreeNode(6,n2,n5)
38 n7 = TreeNode(7,n6,0)
39 n8 = TreeNode(8)
40 root = TreeNode('root',n7,n8)
41
42 bt = BTree(root)
43 print("preOrder".center(50,'-'))
44 print(bt.preOrder(bt.root))
45
46 print("inOrder".center(50,'-'))
47 print (bt.inOrder(bt.root))
48
49 print("postOrder".center(50,'-'))
50 print (bt.postOrder(bt.root))
View Code
堆排序
堆排序，顧名思義，就是基於堆。因此先來介紹一下堆的概念。
堆分為最大堆和最小堆，其實就是完全二叉樹。最大堆要求節點的元素都要大於其孩子，最小堆要求節點元素都小於其左右孩子，兩者對左右孩子的大小關係不做任何要求，其實很好理解。有了上面的定義，我們可以得知，處於最大堆的根節點的元素一定是這個堆中的最大值。其實我們的堆排序演算法就是抓住了堆的這一特點，每次都取堆頂的元素，將其放在序列最後面，然後將剩餘的元素重新調整為最大堆，依次類推，最終得到排序的序列。
堆排序就是把堆頂的最大數取出,
將剩餘的堆繼續調整為最大堆,具體過程在第二塊有介紹,以遞歸實現
剩餘部分調整為最大堆後,再次將堆頂的最大數取出,再將剩餘部分調整為最大堆,這個過程持續到剩餘數只有一個時結束
1 import time,random
2 def sift_down(arr, node, end):
3 root = node
4 #print(root,2*root+1,end)
5 while True:
6 # 從root開始對最大堆調整
7
8 child = 2 * root +1 #left child
9 if child > end:
10 #print('break',)
11 break
12 print("v:",root,arr[root],child,arr[child])
13 print(arr)
14 # 找出兩個child中交大的一個
15 if child + 1 <= end and arr[child] < arr[child + 1]: #如果左邊小於右邊
16 child += 1 #設置右邊為大
17
18 if arr[root] < arr[child]:
19 # 最大堆小於較大的child, 交換順序
20 tmp = arr[root]
21 arr[root] = arr[child]
22 arr[child]= tmp
23
24 # 正在調整的節點設置為root
25 #print("less1:", arr[root],arr[child],root,child)
26
27 root = child #
28 #[3, 4, 7, 8, 9, 11, 13, 15, 16, 21, 22, 29]
29 #print("less2:", arr[root],arr[child],root,child)
30 else:
31 # 無需調整的時候, 退出
32 break
33 #print(arr)
34 print('-------------')
35
36 def heap_sort(arr):
37 # 從最後一個有子節點的孩子還是調整最大堆
38 first = len(arr) // 2 -1
39 for i in range(first, -1, -1):
40 sift_down(arr, i, len(arr) - 1)
41 #[29, 22, 16, 9, 15, 21, 3, 13, 8, 7, 4, 11]
42 print('--------end---',arr)
43 # 將最大的放到堆的最後一個, 堆-1, 繼續調整排序
44 for end in range(len(arr) -1, 0, -1):
45 arr[0], arr[end] = arr[end], arr[0]
46 sift_down(arr, 0, end - 1)
47 #print(arr)
48 def main():
49 # [7, 95, 73, 65, 60, 77, 28, 62, 43]
50 # [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
51 #l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
52 #l = [16,9,21,13,4,11,3,22,8,7,15,27,0]
53 array = [16,9,21,13,4,11,3,22,
