python - 以递归方式对Python列表进行排序

Question

作为输入，我将获得最多可达 n 级的列表列表，并且每次都会有所不同。假设，我有一个列表

[[2, 1, 3], 4, [2, 3], 7, 1, [9, [4, 2], 5]]

这里我想对此列表进行排序，预期输出是

[1, 4, [2, 3], [1, 2, 3], 7, [5, [2, 4], 9]]

这里，首先根据元素进行排序，然后根据列表内元素的总和进行排序。

代码:

input_freq = [[2,1,3],4,[2,3],7,1,[9,[4,2],5]]

res = []

def sortFreq(input_freq):
    elements = []
    list_of_elements = []

    for each in input_freq:
        if isinstance(each, list):
            print "list"
            list_of_elements.append(each)
            each.sort()
        else:
            elements.append(each)
            elements.sort()

    print elements
    print list_of_elements

sortFreq(input_freq)

预期输出:

[1, 4, [2, 3], [1, 2, 3], 7, [5, [4, 2], 9]]

但是我的代码返回错误的结果:

[[1, 2, 3], [2, 3], [5, 9, [4, 2]]]

Answer 1

您必须首先向下移动到嵌套级别，然后在递归调用返回时对父级别进行排序。我假设您想要返回一个新列表(而不是就地排序):

def nested_sort(l):
    def sort_key(e):
        if isinstance(e, list):
            return sum(sort_key(inner) for inner in e)
        return e
    return sorted(
        [nested_sort(e) if isinstance(e, list) else e for e in l],
        key=sort_key)

排序键必须对嵌套列表进行递归求和，因此如果您有许多嵌套级别，这可能会很昂贵。因为可能值得根据求和列表的标识添加缓存:

def nested_sort(l, _sum_cache=None):
    if _sum_cache is None:
        _sum_cache = {}
    def sort_key(e):
        if isinstance(e, list):
            e_id = id(e)
            if e_id not in _sum_cache:
                _sum_cache[e_id] = sum(sort_key(inner) for inner in e)
            return _sum_cache[e_id]
        return e
    return sorted(
        [nested_sort(e, _sum_cache) if isinstance(e, list) else e for e in l],
        key=sort_key)

演示:

>>> nested_sort([[2, 1, 3], 4, [2, 3], 7, 1, [9, [4, 2], 5]])
[1, 4, [2, 3], [1, 2, 3], 7, [5, [2, 4], 9]]