您可以使用堆队列；在O（NlogK）时间中，它可以从大小N的列表中为您提供K个最大或最小的数字。
Python标准库包含
heapq模块，并带有已实现的
heapq.nsmallest()功能：
import heapqk_smallest = heapq.nsmallest(k, input_list)
在内部，这将使用输入列表的前K个元素创建大小为K的堆，然后遍历其余的NK个元素，将每个元素推入堆，然后弹出最大的一个。这样的推入和弹出操作花费日志K时间，从而使总体操作为O（NlogK）。
该功能还优化了以下边缘情况：
- 如果K为1，
min()
则使用该函数，结果为O（N）。 - 如果K> = N，则该函数改用排序，因为在这种情况下O（NlogN）会胜过O（NlogK）。
更好的选择是使用introselect算法，该算法提供O（n）选项。我知道的唯一实现是使用
numpy.partition()功能：
import numpy# assuming you have a python list, you need to convert to a numpy array firstarray = numpy.array(input_list)# partition, slice back to the k smallest elements, convert back to a Python listk_smallest = numpy.partition(array, k)[:k].tolist()
除了需要安装之外
numpy，这还占用了N个内存（相对于K而言
heapq），因为为分区创建了列表的副本。
如果只需要索引，则可以将其用于任一变体：
heapq.nsmallest(k, range(len(input_list)), key=input_list.__getitem__) # O(NlogK)numpy.argpartition(numpy.array(input_list), k)[:k].tolist() # O(N)
