2019-07-06

归并排序

不使用辅助空间:

def mergeSort(a, start, end):
if start >= end:
return mid = start + int((end - start)/2)
mergeSort(a, start, mid)
mergeSort(a, mid+1, end)
merge_local(a, start, mid, end)

def insert(a, start, end):
tmp = a[end]
while end > start:
a[end] = a[end-1]
end -= 1
a[start] = tmp

def merge_local(a, l_i, mid, r_j):
i = l_i
for j in range(mid+1, r_j+1):
while i < j:
if a[j] < a[i]:
insert(a, i, j)
i = i+1
break
else:
i+=1
if i == j:
break

def merge(a, l_i, mid, r_j):
aux = []
i, left, right = 0, l_i, mid+1
while i < r_j - l_i + 1:
if left > mid:
aux.append(a[right])
right+=1
elif right > r_j:
aux.append(a[left])
left+=1
elif a[left] <= a[right]:
aux.append(a[left])
left+=1
else:
aux.append(a[right])
right+=1
i+=1

for k in range(i):
    a[l_i] = aux[k]
    l_i+=1
    k+=1

if name == “main“:
import random
a = [ random.randrange(100) for _ in range(20)]
print(a)
mergeSort(a, 0, len(a)-1)
print(a)

使用n的辅助空间:

def mergeSort(a, start, end):
if start >= end:
return mid = start + int((end - start)/2)
mergeSort(a, start, mid)
mergeSort(a, mid+1, end)
merge(a, start, mid, end)

for k in range(i):
    a[l_i] = aux[k]
    l_i+=1
    k+=1

if name == “main“:
import random
a = [ random.randrange(10) for _ in range(10)]
print(a)
mergeSort(a, 0, len(a)-1)
print(a)