2016 - 2024

感恩一路有你

java递归 一道java面试题,20亿数字的文本排序,如何取前100?

浏览量:2879 时间:2021-03-17 03:02:17 作者:admin

一道java面试题,20亿数字的文本排序,如何取前100?

既然是java题,这就是经典的topk问题。先取前100个数,建立一个最小堆,剩下的数依次从堆顶插入元素,同时调整堆。最后堆中的100个元素即为结果。空间复杂度为k,时间复杂度为nlogk

java如何实现快速排序?

快速排序的原理:选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素。

一次循环:从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换。找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两边就是有序的了。

接着分别比较左右两边的序列,重复上述的循环。

java递归 java排序 快速排序算法详细图解

版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。