基本思想：歸并排序是一種典型的分治思想，把一個無序列表一分為二，對每個子序列再一分為二，繼續(xù)下去，直到無法再進行劃分為止。然后，就開始合并的過程，對每個子序列和另外一個子序列的元素進行比較，依次把小元素放入結(jié)果序列中進行合并，最終完成歸并排序。
歸并操作過程：
申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
重復(fù)步驟3直到某一指針達到序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
上述說法是理論表述，下面用一個實際例子說明：
例如一個無序數(shù)組
|
1
|
[6,2,3,1,7] |
首先將這個數(shù)組通過遞歸方式進行分解，直到：
|
1
|
[6],[2],[3],[1],[7] |
然后開始合并排序，也是用遞歸的方式進行：
兩個兩個合并排序，得到：
|
1
|
[2,6],[1,3],[7] |
上一步中，其實也是按照本步驟的方式合并的，只不過由于每個list中一個數(shù)，不能完全顯示過程。下面則可以完全顯示過程。
初始：
|
1
|
a = [2,6] b = [1,3] c = [] |
第1步，順序從a,b中取出一個數(shù)字：2,1 比較大小后放入c中，并將該數(shù)字從原list中刪除，結(jié)果是：
|
1
|
a = [2,6] b = [3] c = [1] |
第2步，繼續(xù)從a,b中按照順序取出數(shù)字，也就是重復(fù)上面步驟，這次是：2,3 比較大小后放入c中，并將該數(shù)字從原list中刪除，結(jié)果是：
|
1
|
a = [6] b = [3] c = [1,2] |
第3步,再重復(fù)前邊的步驟,結(jié)果是：
|
1
|
a = [6] b = [] c = [1,2,3] |
最后一步，將6追加到c中，結(jié)果形成了：
|
1
|
a = [] b = [] c = [1,2,3,6] |
通過反復(fù)應(yīng)用上面的流程，實現(xiàn)[1,2,3,6]與[7]的合并
最終得到排序結(jié)果
|
1
|
[1,2,3,6,7] |
本文列舉了三種python的實現(xiàn)方法：
方法1：將前面講述的過程翻譯過來了，略先拙笨
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#! /usr/bin/env python#coding:utf-8def merge_sort(seq): if len(seq) ==1: return seq else: middle = len(seq)/2 left = merge_sort(seq[:middle]) right = merge_sort(seq[middle:]) i = 0 #left 計數(shù) j = 0 #right 計數(shù) k = 0 #總計數(shù) while i < len(left) and j < len(right): if left[i] < right [j]: seq[k] = left[i] i +=1 k +=1 else: seq[k] = right[j] j +=1 k +=1 remain = left if i<j else right r = i if remain ==left else j while r<len(remain): seq[k] = remain[r] r +=1 k +=1 return seq |
方法2：在按照順序取數(shù)值方面，應(yīng)用了list.pop()方法，代碼更緊湊簡潔
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#! /usr/bin/env python#coding:utf-8def merge_sort(lst): #此方法來自維基百科 if len(lst) <= 1: return lst def merge(left, right): merged = [] while left and right: merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0)) while left: merged.append(left.pop(0)) while right: merged.append(right.pop(0)) return merged middle = int(len(lst) / 2) left = merge_sort(lst[:middle]) right = merge_sort(lst[middle:]) return merge(left, right) |
方法3：原來在python的模塊heapq中就提供了歸并排序的方法，只要將分解后的結(jié)果導(dǎo)入該方法即可。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#! /usr/bin/env python#coding:utf-8from heapq import mergedef merge_sort(seq): if len(seq) <= 1: return m else: middle = len(seq)/2 left = merge_sort(seq[:middle]) right = merge_sort(seq[middle:]) return list(merge(left, right)) #heapq.merge()if __name__=="__main__": seq = [1,3,6,2,4] print merge_sort(seq) |
