根据第 3 个数字将数字插入排序的元组列表中

Question

假设我有一个列表 A，当我插入元组 B 时，我得到了列表 C。列表 A 是基于每个元组的第 3 个数字排序的列表

简而言之：如何将此元组插入列表 A，同时保持列表根据第 3 个值排序。

INSERT TO NOT SORT 这不是同一个问题 How to sort a list/tuple of lists/tuples by the element at a given index?

因为排序列表太慢了。

A = [(1, 2, 1),(1, 2, 2),(1, 2, 3),(1, 2, 5)]

insert --> B: (1, 2, 4)

C = [(1, 2, 1),(1, 2, 2),(1, 2, 3),(1, 2, 4),(1, 2, 5)]

Answer 1

有效的方法是使用类似于对分的方法。不幸的是，我认为包的原始实现是不可行的，但这个版本支持关键参数：https://github.com/python/cpython/blob/main/Lib/bisect.py

def bisect_left(a, x, lo=0, hi=None, *, key=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(i, x) will
    insert just before the leftmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    # Note, the comparison uses "<" to match the
    # __lt__() logic in list.sort() and in heapq.
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

然后你可以简单地调用

C = A.copy()
C.insert(bisect_left(A, B, key=lambda tup: tup[2]), B)

根据第 3 个数字将数字插入排序的元组列表中

Insert number in a sorted list of tuples based on their 3rd number

python

list

sorting

insert

tuples