我正在关注 CLRS 书,并在我继续使用 python 中实现所有算法,这是合并排序算法。我在一个测试数组上测试了 merge 函数,它可以工作,所以它必须是 merge_sort 函数,但是它与书中的伪代码几乎相同。
def merge_sort(self, array, p, r):
if p < r:
q = int((p + r) / 2)
self.merge_sort(array, p, q)
self.merge_sort(array, q + 1, r)
self.merge(array, p, q , r)
def merge(self, array, p, q, r):
n1 = q - p + 1
n2 = r - q
left = []
right = []
for i in range(0, n1):
left.append(array[p + i])
for j in range (0, n2):
right.append(array[q + j + 1])
left.append(math.inf)
right.append(math.inf)
i = 0
j = 0
for k in range(p, r):
if left[i] <= right[j]:
array[k] = left[i]
i += 1
else:
array[k] = right[j]
j += 1