我有一个整数数组
int array[] = ...
我可以使用
对其进行排序Arrays.sort(array);
但 Arrays.sort 使用快速排序，这有时会导致 O(n^2) 复杂度。我有一个想法将它转换为 List 然后对其进行排序(使用合并排序，因此上限是 O(n log n))，但缺点是它创建了很多对象，因为从 int 到 Integer 的装箱。
我的第三种方法是:
array = Arrays.stream(array).sorted().toArray();
我只在 IntStream 上操作，但不幸的是文档中没有提到复杂性。
我一直在寻找类似的问题，但我只找到了这个 Big-O complexity of java.util.stream.Stream<T>.sorted()这根本没有帮助，因为有两个不同的答案(第一个当然是部分错误的，因为 Arrays.sort 并不总是 O(n log n))。第二个呢？我还没有找到证据。
最佳答案
你应该调查Heapsort ，虽然稍微慢一点，但它保证了 O(n Log n)。 Quicksort vs heapsort
还有课本解释here .
关于java - 如何有效地对 int 数组进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34831420/