如何对值进行排序并将其按降序放入数组？

Question

如何对值进行排序，并将其直接按降序放入for循环本身的数组中，而不是在for循环之后使用sorted函数？

final_lst = []
for row in data:
    score = function_returns_a_score()
    final_lst.append({"score": score})

print(final_lst)
# returns 
# [{"score": 10}, {"score": 40}, {"score": 90}, {"score": 15}]

print(sorted(final_lst, key=lambda k: k['score'], reverse=True))
# returns
# [{'score': 90}, {'score': 40}, {'score': 15}, {'score': 10}]

Answer 1

只需在循环后对数组进行排序：

final_lst = []
for row in data:
    score = function_returns_a_score()
    final_lst.append({"score": row})

final_list.sort(key=lambda k: k["score"], reverse=True)

print(final_lst)
# returns
# [{'score': 90}, {'score': 40}, {'score': 15}, {'score': 10}]

如果出于任何原因，您真的想维护一个排序列表，那么可以考虑使用PriorityQueue和一个包装对象的类来实现自定义比较函数。

Answer 2

您可以创建一个反向bisect函数来获取正确的插入索引。

借用这个答案的密码

def reverse_bisect(a, x, lo=0, hi=None):
    """Return the index at which x could be inserted in a assuming a
    is reverse-sorted.

    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)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return lo

scores = []
for row in data:
    score = function_returns_a_score()
    idx = reverse_bisect(scores, score) # this is the correct index to insert the value
    scores.insert(idx, score)
final_lst = [{"score": score} for score in scores]

复杂性分析：（取N=数组中的元素数）

排序需要O（NlogN）时间。二进制搜索的时间复杂度为O（logN）。为每个元素调用N次，使其再次运行O（NlogN）次。除此之外，N在开始时更小。

空间复杂性：O（N）您在这里占用了额外的空间来存储值，因此您可能也必须考虑到这一点。

下面的答案适用于希望按“正常”（而非相反）顺序插入值的人。

要在正确的索引处插入分数，首先需要知道正确的索引。如果列表被排序（一个空的lit被排序），我们可以使用二进制搜索找到正确的索引来插入一个元素。

您可以使用对分模块找到需要插入分数的索引。

import bisect

final_lst = []
scores = []
for row in data:
    score = function_returns_a_score()
    idx = bisect.bisect(scores, score) # this is the correct index to insert the value
    final_lst.insert(idx, {"score": score})
    scores.insert(idx, score)

Answer 3

可以使用堆队列：

import random
import heapq

final_list = []
for score in random.sample(range(100), 20): # in random order
    # negative because we're sorting in reverse order
    heapq.heappush(final_list, -score)

final_list = [{'score': -heapq.heappop(final_list)} for _ in range(len(final_list))]

样本结果：

[{'score': 95}, {'score': 94}, {'score': 89}, {'score': 72}, {'score': 71}, {'score': 65}, {'score': 60}, {'score': 58}, {'score': 51}, {'score': 50}, {'score': 45}, {'score': 44}, {'score': 36}, {'score': 35}, {'score': 33}, {'score': 26}, {'score': 25}, {'score': 18}, {'score': 6}, {'score': 3}]

我不确定这是否比排序更复杂，但它可以让您随时按排序顺序提取数据：您可以调用heapq。heappop（final_list）当你需要下一个值时——相反，排序是此时此地完成的。

此外，如果你的分数是固定宽度的整数（例如，从0到100的整数），你可以使用基数排序，在这种情况下，它将是O（3n）。