使用 Python 进行归并排序

我找不到任何可用的 Python 3.3 归并排序算法代码,所以我自己做了一个。有什么办法可以加快速度吗?它在大约 0.3-0.5 秒内对 20,000 个数字进行排序

def msort(x):
result = []
if len(x) < 2:
return x
mid = int(len(x)/2)
y = msort(x[:mid])
z = msort(x[mid:])
while (len(y) > 0) or (len(z) > 0):
if len(y) > 0 and len(z) > 0:
if y[0] > z[0]:
result.append(z[0])
z.pop(0)
else:
result.append(y[0])
y.pop(0)
elif len(z) > 0:
for i in z:
result.append(i)
z.pop(0)
else:
for i in y:
result.append(i)
y.pop(0)
return result

已邀请:
第一个改进是简化主循环中的三种情况:不是在某些序列有元素时进行迭代,而是在两个序列都有元素时进行迭代。当离开循环时,其中一个将为空,我们不知道哪个,但我们不在乎:我们将它们附加在结果的末尾。

def msort2(x):
if len(x) < 2:
return x
result = [] # moved!
mid = int(len(x) / 2)
y = msort2(x[:mid])
z = msort2(x[mid:])
while (len(y) > 0) and (len(z) > 0):
if y[0] > z[0]:
result.append(z[0])
z.pop(0)
else:
result.append(y[0])
y.pop(0)
result += y
result += z
return result
第二个优化是避免popping元素。相反,有两个索引:

def msort3(x):
if len(x) < 2:
return x
result = []
mid = int(len(x) / 2)
y = msort3(x[:mid])
z = msort3(x[mid:])
i = 0
j = 0
while i < len(y) and j < len(z):
if y[i] > z[j]:
result.append(z[j])
j += 1
else:
result.append(y[i])
i += 1
result += y[i:]
result += z[j:]
return result
最后的改进在于使用非递归算法对短序列进行排序。在这种情况下,我使用内置sorted函数并在输入的大小小于 20 时使用它:

def msort4(x):
if len(x) < 20:
return sorted(x)
result = []
mid = int(len(x) / 2)
y = msort4(x[:mid])
z = msort4(x[mid:])
i = 0
j = 0
while i < len(y) and j < len(z):
if y[i] > z[j]:
result.append(z[j])
j += 1
else:
result.append(y[i])
i += 1
result += y[i:]
result += z[j:]
return result
对于原始版本,我对 100000 个整数的随机列表进行排序的测量结果为 2.46 秒,msort2 为 2.33,msort3 为 0.60,msort4 为 0.40。作为参考,对所有列表进行排序sorted需要 0.03 秒。

要回复问题请先登录注册