自顶而下
# coding=utf-8
###归并排序
class Merge:
# 额外数组空间
aux = []
def sort(self, arr):
self.aux = [0] * len(arr)
self.sort0(arr, 0, len(arr) - 1)
def sort0(self, arr, low, high):
if low < high:
mid = (low + high) // 2
self.sort0(arr, low, mid)
self.sort0(arr, mid + 1, high)
self.merge(arr, low, mid, high)
def merge(self, arr, low, mid, high):
for i in range(low, high + 1):
self.aux[i] = arr[i]
i = low
j = mid + 1
# 原地归并
for k in range(low, high + 1):
if i > mid:
arr[k] = self.aux[j]
j += 1
elif j > high:
arr[k] = self.aux[i]
i += 1
elif self.aux[j] >= self.aux[i]:
arr[k] = self.aux[i]
i += 1
else:
arr[k] = self.aux[j]
j += 1
自底而上
def sortBu(self, arr):
le = len(arr)
self.aux = [0] * le ##初始化数据大小
n = 1 # 子列表元素数量
while n < le:
for lo in range(0, le - n, 2*n):
#print("low:"+str(lo))
hi = min(lo + n + n - 1, le - 1)
mid = lo + n - 1
self.merge(arr, lo, mid, hi)
n = n + n
