简短的答案
该
heapq.nsmallest（）
函数将整齐，有效地做到这一点：
>>> from heapq import nsmallest>>> s = [1,2,3,4,5,6,7]>>> nsmallest(3, s, key=lambda x: abs(x-6.5))[6, 7, 5]
本质上是这样说的：“给我三个与 6.5 绝对差值最小的输入值”。
算法及其运行时间
用于 nsmallest 的算法对 数据 进行一次传递，随时在内存中保留不超过 n个
最佳值（这意味着它可与任何输入迭代器一起使用，具有缓存效率和空间效率）。
该算法仅在找到新的“最佳”值时才向堆中添加新值。因此，它使进行比较的次数最小化。例如，如果要从1,000,000个随机输入中寻找100个最佳值，则通常进行的比较少于1,008,000（与使用
min（）
查找单个最佳值相比，比较大约多0.8％）。
的 主要功能 为
分钟（） ， nsmallest（） ，和 排序（）
所有保证该键功能在输入可迭代称为每次值一次。这意味着该技术对于n值最近的问题的更复杂和有趣的示例（即听起来最相似，最接近的颜色，最小的差异，最少的基因突变，欧几里得距离等）将非常有效。
无论 nsmallest（） 和 排序（） 将返回一个列表等级排序由贴近（联系结算由值是第一次看到）。
对于那些感兴趣的人，这里和这里都存在对比较预期数量的分析。快速总结：
- 随机输入的平均大小写：
n + k * (log(k, 2) * log(n/k) + log(k, 2) + log(n/k))
- 递增输入的最佳情况：
n + k * log(k, 2)
- 输入下降的最坏情况：
n * log(k, 2)
优化重复查找
@Phylliida在评论中询问如何针对起点不同的重复查找进行优化。关键是对数据进行预排序，然后使用二等分法找到一个小的搜索段的中心：
from bisect import bisectdef k_nearest(k, center, sorted_data): 'Return *k* members of *sorted_data* nearest to *center*' i = bisect(sorted_data, center) segment = sorted_data[max(i-k, 0) : i+k] return nsmallest(k, segment, key=lambda x: abs(x - center))
例如：
>>> s.sort()>>> k_nearest(3, 6.5, s)[6, 7, 5]>>> k_nearest(3, 0.5, s)[1, 2, 3]>>> k_nearest(3, 4.5, s) [4, 5, 3]>>> k_nearest(3, 5.0, s)[5, 4, 6]
这两个 对开（） 和 nsmallest（） 排序的数据占据优势。前者运行 O（log2 k） 时间，而后者运行 O（n） 时间。
