题目描述
对一个整数数组使用归并排序
算法1
(归并排序) $O(n\log(n)$
自底向上的方法,先划分为两个子区间,然后分别对两个子区间排序,再将排序好的子区间进行合并。
Python 代码
n = int(input())
list1 = list(map(int, input().split()))
def merge_sort(list1):
if len(list1) <= 1:
return
mid = len(list1) // 2
L = list1[:mid]
R = list1[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] <= R[j]:
list1[k] = L[i]
i += 1
else:
list1[k] = R[j]
j += 1
k += 1
while i < len(L):
list1[k] = L[i]
k += 1
i += 1
while j < len(R):
list1[k] = R[j]
k += 1
j += 1
if __name__ == "__main__":
merge_sort(list1)
for i in list1:
print(i, end=" ")
python确实更容易规避边界问题
Respect!
niu
👍
最后两个while可以写成:
list1[k:k+len(L)-i]=L[i:]
k+=len(L)-i
list1[k:]=R[j:]
你这个完全没有边界问题 把python的优点发挥地淋漓尽致啊
太牛了。。。比y大的还要好啊 看到你这个我想回去改进快排了