"""
再来一遍
"""
def merge(arr,l,m,r):
# 首先创建两个列表存储数据
n1 = m - l + 1 # 包含中间m元素
n2 = r - m # 不包含中间m元素
L = [0] * n1
R = [0] * n2
# 然后将数据拷贝进来新的临时列表
for i in range(0,n1):
L[i] = arr[l + i] # 注意m元素的包含
for j in range(0,n2):
R[j] = arr[m + 1 +j] # 不包含m元素
# 设置索引
i = 0 # L索引
j = 0 # R索引
k = l # arr索引
# 进行大小比较，归并到arr中
while i < n1 and j < n2:
# L和R中都有元素时
# 将较小的元素放入到arr中
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < n1: # 只剩L时，将L全部加到arr
arr[k] = L[i]
i += 1
k += 1
while j < n2: # 只剩R时，将R全部加到arr
arr[k] = R[j]
j += 1
k += 1
# 没有返回值，只是完成对arr的归并操作
# 递归进行归并排序，先分解，再有序合并
def mergeSort(arr,l,r):
if l < r:
# 分解
m = int((l + r) / 2)
# 递归
mergeSort(arr,l,m)
mergeSort(arr,m+1,r)
# 合并
merge(arr,l,m,r)
return arr
if __name__ == '__main__':
a = [7,8,5,1,44,77,88,5,24,5,5699,2,4,7,1,82,3]
print(mergeSort(a,0,len(a)-1))
Processed:
0.013, SQL:
12
