演算法學習筆記（三）：冒泡排序和歸併排序

（一）    冒泡排序

冒泡排序的作用就是反覆交換相鄰未按次序排列的數據。

 1 #冒泡排序實現,升序版本
 2 def bubbleSort(data):
 3     # 例如：data = [3,2,1], 很明顯迴圈檢查 data[0] > data[0+1]  data[1] > data[1+1] 這2個表達式是否成立就行了
 4     # 不需要也不可能去檢查 data[2] > data[2+1]是否成立，所以第一重for迴圈的執行次數是列表長度 - 1
 5     for i in range(len(data)-1):
 6         # 第二重for迴圈每執行一輪都會排好一個數據，所以下一輪的執行次數在這次的基礎上-1（即-i）
 7         #不減這個i不影響最終的排序結果，就是會運行很多沒必要執行的迴圈，因為已經排好序的數據還一直在比較
 8         for j in range(len(data)-1-i):
 9             if data[j] > data[j+1]:
10                 data[j],data[j+1] = data[j+1],data[j] #交換相鄰的數據
11                 print(j,data)#這個print是為了看輸出，便於理解加上的，實際可以去掉
12     return data
13 
14 A = [11,8,7,3,1]
15 
16 
17 print(bubbleSort(A))

看下麵這張圖，不難發現，第二重for迴圈每一輪迴圈結束後都會排好一個數據

第一輪結束後是：[8, 7, 3, 1, 11]，不難發現，11是排序好了的，所以第二輪的迴圈次數在這次的基礎上-1就行了，即len(data)-1-i

第二輪結束後是：[7, 3, 1, 8, 11]，不難發現，8，11是排序好了的，所以第三輪的迴圈次數在這次的基礎上-1就行了，即len(data)-1-i。後面都是一樣的道理

第三輪結束後。。。。

第四輪結束後。。。。

降序版本

 1 #冒泡排序實現,降序版本
 2 def bubbleSort(data):
 3     for i in range(len(data)-1):
 4         for j in range(len(data)-1-i):
 5             if data[j] < data[j+1]:
 6                 data[j],data[j+1] = data[j+1],data[j] #交換相鄰的數據
 7     return data
 8 
 9 A = [3,2,23,11,8,6,5,10,12,15]
10 
11 
12 print(bubbleSort(A))

（二）    歸併排序

分為2個過程 ：1、分割 2、歸併

例如：對列表[5,2,4,7,1,3,2,6] 進行歸併排序，過程是這樣的

（1）分割：將列表分割，直到列表長度為1，然後開始歸併

（2）歸併：

 1 #分割數據
 2 def mergeSort(A):
 3     #列表長度等於1時，停止分割，返回該列表
 4     if len(A) == 1:
 5         return A
 6     else:
 7         # //運算符返回商的整數部分，例如3//2 ，返回的就是1
 8         #獲取列表元素中間的索引
 9         mid = len(A) // 2
10         left = A[:mid]#截取（列表）索引0到mid之間的數據（不包括索引為mid的數據）
11         right = A[mid:] #截取（列表）索引mid之後的所有數據（包括索引為mid的數據）
12         #遞歸調用自身繼續分割,直到列表長度為1為止
13         L = mergeSort(left)
14         R = mergeSort(right)
15     #調用merge合併數據
16     return merge(L,R)
17 
18 #合併數據
19 def merge(L,R):
20     result = []
21     while len(L) > 0 and len(R)>0:
22         #判斷哪個數據比較大，將比較小的數據添加到result列表中
23         if L[0] <= R[0]:
24             #pop(0)是從列表刪除索引為0的數據並返回
25             result.append(L.pop(0))
26         else:
27             result.append(R.pop(0))
28     #其中一個列表的數據為空後會退出while迴圈，將另一個列表的數據直接添加到result中
29     result.extend(L)
30     result.extend(R)
31     return result
32 
33 A = [5,2,4,7,1,3,2,6]
34 
35 
36 print(mergeSort(A))