快速按升序和降序排序的有效方法

Question

在下面的代码中，我使用函数generator，它创建随机数并帮助模拟传入的数据。在

from random import randint


def generator(n=1000):
    i = 0
    while i < n:
        yield randint(0, n)
        i += 1

为了按升序排序，只获取最低的10条记录，我使用以下方法：

^{pr2}$

有没有一种更有效、更好的方法来对生成的数据进行排序？，如何按降序排列？在

输入是一个恒定的流，但我只需要保留最低和最高的10个记录。在

Answer 1

使用^{}和^{}函数；这些函数使用堆来有效地跟踪最大或最小的K项：

import heapq

out = heapq.nsmallest(10, generator())

堆不变量是在O（logK）复杂度中维护的，其中K是大小（这里是10）；函数nsmallest创建一个大小为K的堆，用前K个元素填充它，然后在一个操作中将下一个值推送到堆中，每次都弹出最大值。在

在N个元素上循环会使总操作为O（N logK），而排序将需要O（N logN）。如果K小于N，则heapq方法获胜。在

一旦生成器耗尽，堆将按排序顺序返回。在