python - 根据列表中的多个元素对列表进行排序

Question

是否可以实现一个 python 键来根据多个列表元素进行排序？

例如:

list = [1, 2, 3, 4]

我想根据两个元素之间的差异对列表进行排序，以便它们之间的差值最大化。

预期结果:

list = [1, 4, 2, 3] # delta = 4-1 + 4-2 + 3-2 = 6

其他结果也是可能的，但是在原始数组中 1 在 4 之前，所以应该先取 1:

list = [4, 1, 3, 2] # delta = 4-1 + 3-1 + 3-2 = 6

我想像这样使用 python sorted:

sorted(list, key=lambda e1, e2: abs(e1-e2))  

有没有可能这样做呢？也许还有另一个库可以使用。

Answer 1

因为(正如您向我们展示的那样)可能有多种不同的结果 - 这意味着这种排序/顺序不是确定性的，因此您不能对其应用键函数。

也就是说，自己实现排序很容易:

def my_sort(col):
    res = []
    while col:
        _max = max(col)
        col.remove(_max)
        res.append(_max)

        if col:
            _min = min(col)
            col.remove(_min)
            res.append(_min)

    return res


print(my_sort([1,2,3,4]))  # [4, 1, 3, 2]

此解决方案在 O(n^2) 中运行但可以通过排序来改进 col在一开始然后而不是寻找max和 min我们可以提取列表开头和结尾的项目。通过这样做，我们会将时间复杂度降低到 O(n log(n))

编辑

根据您在下面的评论:如果索引起作用，那么它不是“真正的”排序 :) 也就是说，可以设计此解决方案以首先保留较小的索引等等:

def my_sort(col):
    res = []
    while col:
        _max = max(col)
        max_index = col.index(_max)
        col.remove(_max)

        if col:
            _min = min(col)
            min_index = col.index(_min)
            col.remove(_min)
            if max_index < min_index:
                res.extend([_max, _min])
            else:
                res.extend([_min, _max])
            continue
        res.append((_max))

    return res

print(my_sort([1,2,3,4])) # [1, 4, 2, 3]