公认最好的排序算法 一道java面试题，20亿数字的文本排序，如何取前100？

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

因为这是一个Java问题，所以这是典型的TOPK问题。首先取前100个数字构建一个最小堆，然后依次从堆的顶部插入剩余的数字，同时调整堆。堆中最后100个元素就是结果。空间复杂度是k，时间复杂度为nlogk

排序算法有：冒泡排序-O（n^2）鸡尾酒排序-O（n^2）插入排序-O（n^2）桶排序-O（n）O（k）计数排序-O（n k）O（n k）O（n k）合并排序-O（NLog n）需要O（n）额外空间合并排序-O（n^2）二叉树排序-O（NLog n）期望时间；O（n^2）最差时间时间；鸽子洞排序-O（nk）需要O（k）额外的空间

这个问题的最佳时间复杂度是O（n）。所以如果一定要使用排序算法，如果标题条件允许，请尽量选择o（n）排序算法如bucket排序。另一种解决方案是构建一个大小为10的堆，按顺序遍历数组，并在堆满时移除最上面的元素。这样，最多可获得10个元素。时间复杂度为O（nlog10）。

公认最好的排序算法 冒泡排序c++代码 桶排序时间复杂度

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