我正在尝试用 Python 编写一个接受列表和比较函数的合并排序函数:
def sort(unsorted, comp_func=lambda x, y: x < y):
length = len(unsorted)
if length <= 1: return unsorted
halflen = length / 2
lsorted= sort(unsorted[:halflen])
rsorted = sort(unsorted[halflen:])
combined = []
while True:
if len(lsorted) > 0:
if len(rsorted) > 0 and comp_func(rsorted[0], lsorted[0]):
combined.append(rsorted[0])
rsorted = rsorted[1:]
else:
combined.append(lsorted[0])
lsorted = lsorted[1:]
elif len(rsorted) > 0:
combined.append(rsorted[0])
rsorted = rsorted[1:]
else:
break
return combined
当比较函数比较这样的元组。
comp_func = lambda x, y: x[0] < y[0]
但是当我编写比较函数来比较元组的第二个元素时，返回的列表仍然是未排序的版本。
comp_func = lambda x, y: x[1] < y[1]
但是，如果我将“<”运算符更改为“>”以便列表按递减方式排序，它会起作用:
comp_func = lambda x, y: x[1] > y[1]
不知道为什么 '<' 在元组的第二个元素上失败......
在寻找可能的解释后，我发现了这个:Does python think 10 is less than 9 .然而，事实并非如此；正在排序的列表包含 int 的元组，而不是 string。
请您参考如下方法:
您实际上并没有显示您如何更改运算符的记录，所以这只是一个猜测，但请注意这两行
lsorted= sort(unsorted[:halflen])
rsorted = sort(unsorted[halflen:])
不要传递 comp_func。所以如果你做了这样的事情:
>>> sort([(3,4),(1,2), (2,3)])
[(1, 2), (2, 3), (3, 4)]
>>> sort([(3,4),(1,2), (2,3)],lambda x,y: x[1] > y[1])
[(3, 4), (1, 2), (2, 3)]
您会得到不一致的结果，因为有一半时间它使用不同的 comp_func 进行排序。在 lsorted= 和 rsorted= 行中传递 comp_func 解决了这个问题:
>>> sort([(3,4),(1,2), (2,3)],lambda x,y: x[1] > y[1])
[(3, 4), (2, 3), (1, 2)]
