n_largest_num.py

"""
问题8： 100w个数中找出最大的100个数。时间复杂度尽可能的小
方案1：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后一次扫描剩余的元素x，与排好序的100个元素中最小的元素比，
       如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。
       依次循环，知道扫描了所有的元素。复杂度为O(100w*100)。
方案2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比100多的时候，采用传统排序算法排序，
       取前100个。复杂度为O(100w*100)。
方案3：在前面的题中，我们已经提到了，用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。
"""
代码实现如下：
import heapq    #引入堆模块
import random   #产生随机数
test_list = []  #测试列表
for i in range(1000000):                #产生100w个数，每个数在【0,1000w】之间
    test_list.append(random.random()*100000000)
heapq.nlagest(10,test_list)             #求100w个数最大的10个数
heapq.nsmallest(10,test_list)           #求100w个数最小的10个数