归并排序
基于分治,稳定
$$ 时间复杂度:O(nlog_2n) $$
- 确定分界点
(坐标)
mid = (l + r) / 2
- 递归排序左右两边
- 归并,合二为一(重点)
下标方法
其中
if l >= r: return
中的l >= r
可以换成l == r
n = int(input())
alist = list(map(int,input().split()))
def mergeSort(q, l, r):
if l == r: return
mid = l + r >> 1
mergeSort(q, l, mid)
mergeSort(q, mid + 1, r)
i = l
j = mid + 1
res = []
while i <= mid and j <= r:
if q[i] <= q[j]:
res.append(q[i])
i += 1
else:
res.append(q[j])
j += 1
while i <= mid:
res.append(q[i])
i += 1
while j <= r:
res.append(q[j])
j += 1
q[l:r+1] = res
mergeSort(alist, 0, n - 1)
for i in alist:
print(i, end=' ')