<reponame>bigfoolliu/liu_aistuff<gh_stars>1-10
#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# author: bigfoolliu


"""
问题8： 100w个数中找出最大的100个数。时间复杂度尽可能的小
方案1：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后每次取出剩余的元素集合中的一个元素，与排好序的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)

ret1 = heapq.nlargest(10, test_list)  # 求100w个数最大的10个数
ret2 = heapq.nsmallest(10, test_list)  # 求100w个数最小的10个数

print(ret1, ret2)

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# author: bigfoolliu


"""
问题8： 100w个数中找出最大的100个数。时间复杂度尽可能的小
方案1：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后每次取出剩余的元素集合中的一个元素，与排好序的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)

ret1 = heapq.nlargest(10, test_list)  # 求100w个数最大的10个数
ret2 = heapq.nsmallest(10, test_list)  # 求100w个数最小的10个数

print(ret1, ret2)
#!/usr/bin/env python3 # -*- coding:utf-8 -*- # author: bigfoolliu 问题8： 100w个数中找出最大的100个数。时间复杂度尽可能的小 方案1：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后每次取出剩余的元素集合中的一个元素，与排好序的100个元素中最小的元素比，        如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。        依次循环，直到扫描了所有的元素。复杂度为O(100w*100)。 方案2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，直到比轴大的一部分在比100多的时候，采用传统排序算法排序，        取前100个。复杂度为O(100w*100)。 方案3：在前面的题中，我们已经提到了，用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。 代码实现如下： # 引入堆模块 # 产生随机数 # 测试列表 # 产生100w个数，每个数在【0,1000w】之间 # 求100w个数最大的10个数 # 求100w个数最小的10个数