The Divide and Conquer Approach - 归并排序 _conquer

历览千载书，时时见遗烈。这篇文章主要讲述The Divide and Conquer Approach - 归并排序相关的知识，希望能为你提供帮助。

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

【The Divide and Conquer Approach - 归并排序】