目錄

一. 冒泡排序

二. 歸并排序

---

一. 冒泡排序

冒泡排序（Bubble Sort）也是一種簡(jiǎn)單直觀的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢"浮"到數(shù)列的頂端。

def bubbleSort(arr):n = len(arr)# 遍歷所有數(shù)組元素for i in range(n):# Last i elements are already in placefor j in range(0, n-i-1):if arr[j] > arr[j+1] :arr[j], arr[j+1] = arr[j+1], arr[j]arr = [64, 34, 25, 12, 22, 11, 90]bubbleSort(arr)print ("排序后的數(shù)組:")
for i in range(len(arr)):print ("%d" %arr[i]),

執(zhí)行以上代碼輸出結(jié)果為：

排序后的數(shù)組:
11
12
22
25
34
64
90

二. 歸并排序

歸并排序（英語：Merge sort，或mergesort），是創(chuàng)建在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

分治法:

• 分割：遞歸地把當(dāng)前序列平均分割成兩半。
• 集成：在保持元素順序的同時(shí)將上一步得到的子序列集成到一起（歸并）。

def merge(arr, l, m, r): n1 = m - l + 1n2 = r- m # 創(chuàng)建臨時(shí)數(shù)組L = [0] * (n1)R = [0] * (n2)# 拷貝數(shù)據(jù)到臨時(shí)數(shù)組 arrays L[] 和 R[] for i in range(0 , n1): L[i] = arr[l + i] for j in range(0 , n2): R[j] = arr[m + 1 + j] # 歸并臨時(shí)數(shù)組到 arr[l..r] i = 0     # 初始化第一個(gè)子數(shù)組的索引j = 0     # 初始化第二個(gè)子數(shù)組的索引k = l     # 初始?xì)w并子數(shù)組的索引while i < n1 and j < n2 : if L[i] <= R[j]: arr[k] = L[i] i += 1else: arr[k] = R[j] j += 1k += 1# 拷貝 L[] 的保留元素while i < n1: arr[k] = L[i] i += 1k += 1# 拷貝 R[] 的保留元素while j < n2: arr[k] = R[j] j += 1k += 1def mergeSort(arr,l,r): if l < r: m = int((l+(r-1))/2)mergeSort(arr, l, m) mergeSort(arr, m+1, r) merge(arr, l, m, r) arr = [12, 11, 13, 5, 6, 7] 
n = len(arr) 
print ("給定的數(shù)組") 
for i in range(n): print ("%d" %arr[i]), mergeSort(arr,0,n-1) 
print ("\n\n排序后的數(shù)組") 
for i in range(n): print ("%d" %arr[i]),

執(zhí)行以上代碼輸出結(jié)果為：

給定的數(shù)組
12
11
13
5
6
7排序后的數(shù)組
5
6
7
11
12
13