1 The divide and conquer approach - 归并排序   2     归并排序所应用的理论思想叫做分治法.  3     分治法的思想是: 将问题分解为若干个规模较小,并且类似于原问题的子问题,  4     然后递归(recursive) 求解这些子问题, 最后再合并这些子问题的解以求得  5     原问题的解.  6         即, 分解 -> 解决 -> 合并.  7   8     The divide and conquer approach   9         分解: 将待排序的含有 n 个元素的的序列分解成两个具有 n/2 的两个子序列. 10         解决: 使用归并排序递归地排序两个子序列. 11         合并: 合并两个已排序的子序列得出结果. 12  13     归并排序算法的 '时间复杂度' 是 nlogn 14  15 import time, random 16  17 def sortDivide(alist):     # 分解 divide 18     if len(alist) <= 1: 19         return alist 20     l1 = sortDivide(alist[:alist.__len__()//2]) 21     l2 = sortDivide(alist[alist.__len__()//2:]) 22     return sortMerge(l1,l2) 23  24 def sortMerge(l1, l2):     # 解决 & 合并  sort & merge 25     listS = [] 26     print("Left - ", l1) 27     print("Right - ", l2) 28     i,j = 0,0 29     while i < l1.__len__() and j < l2.__len__(): 30         if l1[i] <= l2[j]: 31             listS.append(l1[i]) 32             i += 1 33             print("-i", i) 34         else: 35             listS.append(l2[j]) 36             j += 1 37             print("-j", j) 38         print(listS) 39     else: 40         if i == l1.__len__(): 41             listS.extend(l2[j:]) 42         else: 43             listS.extend(l1[i:]) 44         print(listS) 45     print("Product -",listS) 46     return listS 47  48 def randomList(n,r): 49     F = 0 50     rlist = [] 51     while F < n: 52         F += 1 53         rlist.append(random.randrange(0,r)) 54     return rlist 55  56 if __name__ == "__main__": 57     alist = randomList(9,100) 58     print("List-O",alist) 59     startT =time.time() 60     print("List-S", sortDivide(alist)) 61     endT = time.time() 62     print("Time elapsed :", endT - startT) 63  64 output, 65     List-O [88, 79, 52, 78, 0, 43, 21, 55, 62] 66     Left -  [88] 67     Right -  [79] 68     -j 1 69     [79] 70     [79, 88] 71     Product - [79, 88] 72     Left -  [52] 73     Right -  [78] 74     -i 1 75     [52] 76     [52, 78] 77     Product - [52, 78] 78     Left -  [79, 88] 79     Right -  [52, 78] 80     -j 1 81     [52] 82     -j 2 83     [52, 78] 84     [52, 78, 79, 88] 85     Product - [52, 78, 79, 88] 86     Left -  [0] 87     Right -  [43] 88     -i 1 89     [0] 90     [0, 43] 91     Product - [0, 43] 92     Left -  [55] 93     Right -  [62] 94     -i 1 95     [55] 96     [55, 62] 97     Product - [55, 62] 98     Left -  [21] 99     Right -  [55, 62]100     -i 1101     [21]102     [21, 55, 62]103     Product - [21, 55, 62]104     Left -  [0, 43]105     Right -  [21, 55, 62]106     -i 1107     [0]108     -j 1109     [0, 21]110     -i 2111     [0, 21, 43]112     [0, 21, 43, 55, 62]113     Product - [0, 21, 43, 55, 62]114     Left -  [52, 78, 79, 88]115     Right -  [0, 21, 43, 55, 62]116     -j 1117     [0]118     -j 2119     [0, 21]120     -j 3121     [0, 21, 43]122     -i 1123     [0, 21, 43, 52]124     -j 4125     [0, 21, 43, 52, 55]126     -j 5127     [0, 21, 43, 52, 55, 62]128     [0, 21, 43, 52, 55, 62, 78, 79, 88]129     Product - [0, 21, 43, 52, 55, 62, 78, 79, 88]130     List-S [0, 21, 43, 52, 55, 62, 78, 79, 88]131     Time elapsed : 0.0010027885437011719