如何高效地对整数数组进行排序

Question

我有一个int数组

int array[] = ...

我可以使用

进行排序。

Arrays.sort(array);

但是 Arrays.sort 使用快速排序，有时会导致 O(n^2) 复杂度。我有一个想法，将其转换为 List 然后进行排序（使用归并排序，因此上限为 O(n log n)），但缺点是由于从 int 到 Integer 的装箱而创建了大量对象。

我的第三种方法是这样的：

array = Arrays.stream(array).sorted().toArray();

我只在IntStream上操作，但不幸的是文档中没有提到复杂度。我正在寻找类似的问题，只找到了这个java.util.stream.Stream.sorted()的Big-O复杂度，但它并不有用，因为有两个不同的答案（第一个当然部分错误，因为Arrays.sort并不总是O(n log n)）。那第二个呢？我没有找到证明。

- Pand

---

根据 Arrays.sort 的 Javadoc：“对于许多导致其他快速排序算法退化为二次性能的数据集，此算法提供 O(n log(n)) 的性能，并且通常比传统的（单个枢轴）快速排序实现更快。” 你的前提是错误的。 - Tunaki

我投票关闭此问题，因为原提问者错误地阅读了文档，不符合主题。 - Denys Séguret

@Tunaki 他的前提并没有错。虽然与其他算法相比，该实现可能不会经常表现出*O(n^2)*的行为，但它无法避免在某些数据集上表现出这种行为。 - user207421

所有这些踩票真的有必要吗？ - sinclair

说Arrays.sort不是O(n log n)当然是正确的。最坏情况下的复杂度是O(n^2)，如果有一个包含10^6个元素的数组，它可能会运行数年... - Pand

Answer 1

你应该了解堆排序，虽然它稍微慢一些，但保证了O(n Log n)。快速排序 vs 堆排序 还有教科书上的解释这里。

- Chad Dienhart

Answer 2

如果整数范围较小，您可以使用计数排序，它使用数字作为数组索引，并且与具有O（nlogn）下限的比较排序算法（例如快速排序或归并排序）不同，其复杂度为O（n+k），其中k是最小值和最大值之间的范围。

选择哪种算法始终取决于您可能了解的有关数组元素分布的任何额外知识。

- Kostas Kryptos

---

我知道，但整数范围很大。 - Pand

Answer 3

O(n) 时间复杂度，O(1) 空间复杂度

使用来自 fastutil 库的 IntArrays.unstableSort(int[] a)。

它对于足够大的数组使用原地基数排序，对于小数组使用快速排序：

if (to - from >= RADIX_SORT_MIN_THRESHOLD) {
  radixSort(a, from, to);
} else {
  quickSort(a, from, to);
}

O(n log(n))时间复杂度，O(n)空间复杂度和Java 14+

Arrays.sort使用快速排序算法，有时会导致O(n^2)的时间复杂度。

只有在使用Java 13或更早版本时才会发生。从Java 14开始，Arrays.sort(int[])保证在最坏情况下具有O(n log(n))的性能：

该算法在所有数据集上都提供O(n log(n))的性能，并且通常比传统的（单轴）快速排序实现更快。

https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Arrays.html#sort(int%5B%5D)

如果递归深度过大，则通过堆排序来实现。

if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
  heapSort(a, low, high);
  return;
}

- Denis Stafichuk

Answer 4

自己实现归并排序，这并不是什么高深的科学。

在你实现完之后，花点时间运行一些基准测试，并将你的实现与Arrays.sort的性能进行比较。也许会有一些惊喜等着你。

此外，阅读关于过早优化的文章，我认为你可能会发现这个概念很有用。

- Dima

---

我毫不怀疑唐·纳森会感到惊讶，因为选择排序算法被认为是“过早优化”。 - user207421

@EJP，你会吗？为什么？你认为他不会考虑选择一种排序算法作为“优化”吗？你的惊讶肯定与术语的另一部分无关，因为某物具有“过早”的属性并不取决于该行动的性质，而只取决于其时间。我真的很困惑。你在这里有什么反对意见？ - Dima

当然，我可以自己实现它，但是我认为首先检查是否已经有了相应的实现会更好。我知道关于过早优化的问题，但是如果数组中有约10^6个元素，我不能使用Arrays.sort，因为对于某些数据集，它可能需要运行几年才能完成。 - Pand

@Pand你为什么这么认为？你有这样的数据集示例吗？ - Dima

现在我没有，但是可能会出现这种情况。我曾经在在线评测平台Codeforces上遇到过这种情况，因为使用Arrays.sort而不是排序列表导致了时间限制。你可以在这里阅读更多信息：http://codeforces.com/blog/entry/7108 - Pand

一切皆有可能……嗯，几乎是这样。"现在我没有"是过早优化的定义。 - Dima