AcWing 107. 超快速排序,归并排序,Python
原题链接
简单
作者:
BRANTILLI
,
2022-05-01 20:45:43
,
所有人可见
,
阅读 199
def merge_sort(q,l,r):
if l >= r:
return 0
mid = l +r >>1
res = merge_sort(q,l,mid) + merge_sort(q,mid+1,r)
i, j = l, mid+1
temp = []
while i <= mid and j <= r:
if q[i] <= q[j]:
temp.append(q[i])
i += 1
else:
temp.append(q[j])
j += 1
res+=mid -i +1
while i <= mid:
temp.append(q[i])
i += 1
while j <= r:
temp.append(q[j])
j+=1
for i in range(r-l +1):
q[l+i] = temp[i]
return res
while 1:
n = int(input())
arr = []
if n == 0:
break
for i in range(n):
arr.append(int(input()))
print(merge_sort(arr,0,n -1))