求最大数的问题

显示全部楼层 · 2021-1-27 06:48:00

一个算法的问题，假设现在有5组数，每组里面有1到10000个数不等，如何才能从编程获取其中最大的100个数呢？怎么才能让效率高点呢？
分 -->

千问 · 2021-1-27 06:48:00

我比较习惯是用冒泡排序法,即两两做比较,将大的数字放前面，小的放后面,直至比较完一次，然后第二次扫描数列,重复如此,可以得到一个从大到小的数列.如果LZ想要效率点的，可以参考《算法与数据结构》一书，大学里的教科用书，呵呵，里面有各种算法~

千问 · 2021-1-27 06:48:00

弄个容量为100的小顶堆，每次新来的数字都和堆顶比较，大过堆顶就删除堆顶，然后该元素进堆，小于等于就直接丢了。算法复杂度O(n(log100)),n为总数字个数
如果知道这些数的范围（比如引用5楼litaoye的回复:混在一起用nth_element获取第100个数,用堆排也可以,不过不用全排完,只要排出前100个。
也可以从每组中找出前100个，然后做4次归并排序！
不对。每组可不保证都大于100，应该是五组串行地遍历，并行会出问题。

千问 · 2021-1-27 06:48:00

元素个数少于100的组就全上吧,总之是4次归并。
引用6楼hikaliv的回复:引用5楼litaoye的回复:
混在一起用nth_element获取第100个数,用堆排也可以,不过不用全排完,只要排出前100个。
也可以从每组中找出前100个，然后做4次归并排序！
不对。每组可不保证都大于100，应该是五组串行地遍历，并行会出问题。

千问 · 2021-1-27 06:48:00

引用7楼litaoye的回复:元素个数少于100的组就全上吧,总之是4次归并。

引用6楼hikaliv的回复:
引用5楼litaoye的回复:
混在一起用nth_element获取第100个数,用堆排也可以,不过不用全排完,只要排出前100个。
也可以从每组中找出前100个，然后做4次归并排序！
不对。每组可不保证都大于100，应该是五组串行地遍历，并行会出问题。
嗯……又想了想，此法不错。可以保证稳定性。
不过串行遍历是线性复杂度，而并行的话，反而是o(nlogn)，我没算错吧。

千问 · 2021-1-27 06:48:00

用堆

千问 · 2021-1-27 06:48:00

时间复杂度上应该都差不多，合为一组用堆排是n+100*log(n)，分组的话也差不太多(n+100*(logn1+logn2+logn3+logn4+logn5)),归并虽然会慢一些,
但只有4次,基本上属于常数（引用8楼hikaliv的回复:引用7楼litaoye的回复:
元素个数少于100的组就全上吧,总之是4次归并。

引用6楼hikaliv的回复:
引用5楼litaoye的回复:
混在一起用nth_element获取第100个数,用堆排也可以,不过不用全排完,只要排出前100个。
也可以从每组中找出前100个，然后做4次归并排序！
不对。每组可不保证都大于100，应该是五组串行地遍历，并行会出问题。

嗯……又想了想，此法不错。可以保证稳定性。
不过串行遍历…