python list 合并，[轉載] 算法導論：分治法，python實現合并排序MERGE-SORT

參考鏈接： Python中的合并排序merge sort

1. 簡單合并排序法實現

思想：兩堆已排好的牌，牌面朝下，首先掀開最上面的兩張，比較大小取出較小的牌，然后再掀開取出較小牌的那一堆最上面的牌和另一堆已面朝上的牌比較大小，取出較小值，依次類推......

?

"""合并兩個已經排好的子列表"""

python list 合并。?

ListB = [2, 4, 5, 7, 1, 2, 3, 6]

?

ListB_L = ListB[0: int((len(ListB))/2)]

ListB_R = ListB[int((len(ListB))/2): len(ListB)]? # 把列表B分為左右兩塊，可以發現L和R已經排好序了

?

python合并兩個有序列表、ListB_L.append(99999)

ListB_R.append(99999)? # 在每個子列表的底部放置哨兵牌

?

i = 0

j = 0

for n in range(0, len(ListB)):

python合并多個excel、? ? if ListB_L[i] <= ListB_R[j]:

? ? ? ? ListB[n] = ListB_L[i]

? ? ? ? i = i + 1? ? ? ? ? ? ? ? ? ?# 依次取兩個子列表的較小值填入列表B中

? ? else:

? ? ? ? ListB[n] = ListB_R[j]

? ? ? ? j = j + 1

python降序排列，print(ListB)

2. 合并排序元素個數為2的冪數的列表

思想：將原始列表中的元素，拆分為個數為2的子列表，將每個子列表進行合并排序，加以整合變為左右兩部分都排好序的元素個數為4的子列表.......

?

"""合并長度為2的冪數的無序列表"""

?

序列重排 python，B1 = [2, 1, 5, 7, 4, 2, 3, 6]

def MERGE_SORT(B):

? ? # 定義合并排序函數

? ? L = B[0: int((len(B)) / 2)]

? ? R = B[int((len(B)) / 2): len(B)]??

?

python與excel結合、? ? L.append(99999)

? ? R.append(99999)? # 在每個子列表的底部放置哨兵牌

?

? ? i = 0

? ? j = 0

? ? for n in range(0, len(B)):

python處理excel數據，? ? ? ? if L[i] <= R[j]:

? ? ? ? ? ? B[n] = L[i]

? ? ? ? ? ? i = i + 1? ? ? ? ? ? ? ? ? ?# 依次取兩個子列表的較小值填入列表B中

? ? ? ? else:

? ? ? ? ? ? B[n] = R[j]

? ? ? ? ? ? j = j + 1

python excel、? ? return(B)

?

def dividelist(B0):

? ? L0 = B0[0: int((len(B0)) / 2)]

? ? R0 = B0[int((len(B0)) / 2): len(B0)]? # 定義拆分函數，把列表分為左右兩個子列表

? ? return L0, R0

python元祖、?

L1, R1 = dividelist(B1)

LL1, RL1 = dividelist(L1)? ? ? ? ? ?# 這部分最終將8個數的列表分為，4個2個元素的子列表

LR1, RR1 = dividelist(R1)

?

MERGE_SORT(LL1)

python編程，MERGE_SORT(RL1)? ? ? ? ? ? ?# 調用合并排序函數，把元素個數為2的4個子列表各自排好序

MERGE_SORT(LR1)

MERGE_SORT(RR1)

?

L1 = LL1 + RL1

R1 = LR1 + RR1? ? ? ? ? ? # 將排好序的4個子列表兩兩合并為元素個數為2的左右兩部分都排好序的子列表

排序算法 Python。?

MERGE_SORT(L1)

MERGE_SORT(R1)? ? ? ? ? ?# 把元素個數為4的兩個子列表排好序

?

B1 = L1 + R1? ? ? ? ? ? # 合并為一個元素個數為8的即包含原始列表所有元素的左右兩部分都排好序的完整列表

MERGE_SORT(B1)? ? ? ? ?# 調用合并排序函數，得到最終結果

python 數據分析，?

print(B1)存在的問題，拆分和整合部分由于自己目前能力不足，手動寫了一下。但根據分治法的原理，整個算法的運行速度比普通排序要快，時間復雜度為O(n*lgn)，插入排序法時間復雜度為O(n^2)。

?

3. 用Python實現任意排列數組的合并排序

?

?

python merge？"""Python實現合并排序"""

?

?

def MERGE(A, p, q, r):

? ? """定義合并函數"""

? ? n1 = q - p

python歸并排序算法。? ? n2 = r - q

?

? ? L = []

? ? R = []? ?# 定義左右兩個空數組

?

? ? for i in range(0, n1):

python排列組合算法。? ? ? ? L.append(A[p + i])

? ? for j in range(0, n2):

? ? ? ? R.append(A[q + j])

?

? ? L.append(float('inf'))

? ? R.append(float('inf'))? ? # 添加哨兵牌

python 合并列表、? ? i = 0

? ? j = 0

? ? for n in range(p, r):

? ? ? ? if L[i] <= R[j]:

? ? ? ? ? ? A[n] = L[i]

? ? ? ? ? ? i = i + 1

歸并排序 python。? ? ? ? else:

? ? ? ? ? ? A[n] = R[j]

? ? ? ? ? ? j = j + 1

? ? return A

?

?

def MERGE_SORT(A, p, r):

? ? """定義MERGE_SORT函數，對一個數列實現合并排序"""

? ? if p + 1 < r:

? ? ? ? q = int((p + r)/2)

? ? ? ? MERGE_SORT(A, p, q)? ?# 調用MERGE子函數

? ? ? ? MERGE_SORT(A, q, r)

? ? ? ? MERGE(A, p, q, r)? # 調用MERGE函數實現左右兩部分已排好序的數列的合并

? ? return A

?

?

A = [4, 1, 2, 6, 3, 2, 5, 7]

C = MERGE_SORT(A, 0, len(A))

print(C)