python - 使用排序技术时出现类型错误

Question

当我尝试在合并排序函数中使用递归时，出现类型错误。我试图返回一个包含列表和数字的元组。但是，如果仅返回列表，那么我的函数就能够正确排序并返回排序的列表。

我想要的输出:

([1,2,3,4,5,6,7,8,9,10,...],100)

我的合并函数采用列表和简单的 lambda 表达式来比较两个数字。

def merge_s(list_s, ordering):

    if len(list_s) < 2:
        return list_s, 100
    result = []
    mid = int(len(list_s) / 2)
    y = merge_s(list_s[:mid], ordering)
    z = merge_s(list_s[mid:], ordering)
    i = 0
    j = 0
    first_item = ''
    second_item = ''

    while i < len(y) and j < len(z):
        first_item = y[i]
        second_item = z[j]
        if ordering(second_item, first_item):
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    return result, 100

我的主要功能:

from random import shuffle
def main():

    for i in range(10):
        data = list(range(100))
        shuffle(data)
        comp = lambda a, b: a < b #my compare function
        (sorted_data, _) = merge_s(data, comp)
        test = (sorted_data,_)
    print(test)

但是，我收到错误:

TypeError: '<' not supported between instances of 'int' and 'list'

Answer 1

merge_s 返回:结果，100

但是，当您获得递归调用的结果时:

y = merge_s(list_s[:mid], ordering)
z = merge_s(list_s[mid:], ordering)

您将其视为 merge_s 刚刚返回 result 而不是 (result, 100) 的元组

while i < len(y) and j < len(z):
    first_item = y[i]
    second_item = z[j]
    if ordering(second_item, first_item):

这有一个非常简单的修复，您只需提取 y 和 z 的结果即可:

y, _ = merge_s(list_s[:mid], ordering)
z, _ = merge_s(list_s[mid:], ordering)

修复后，您的输出是:

([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99], 100)