Java 6中有哪些不同的排序算法可用？

Question

有几种排序算法，如插入排序、选择排序、冒泡排序等，经常在计算机科学教科书中讨论。如果给定一组整数或对象数组，是否有内置的Java 6语言API可以让我选择应用特定的排序算法来对数组进行排序，而不是我再次重复造轮子？如果Java 6没有内置此功能，是否有开源库提供此功能，它们是什么？

- ace

---

请注意，这在Java 7中是不同的 - 请参见https://dev59.com/o2865IYBdhLWcg3wCqBA - Thorbjørn Ravn Andersen

@amc，您有48个问题没有被采纳的答案。也许您可以跟进一下答案，以便它们能够被采纳。 - Peter Lawrey

Answer 1

Arrays.sort()方法在所有基本类型的数组中使用快速排序。

排序算法是一个经过调整的快速排序，改编自Jon L. Bentley和M. Douglas McIlroy的“Engineering a Sort Function”，Software-Practice and Experience，Vol.23(11)P.1249-1265（1993年11月）。该算法在许多数据集上提供n*log(n)性能，而其他快速排序算法会降级到二次性能。

Collections.sort()方法使用合并排序。此排序也用于Arrays.sort(Object[])和Arrays.sort(T[], Comparator<? super T>)。

排序算法是修改过的归并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）。该算法提供了保证的n log(n)性能。此实现将指定的列表转储到数组中，对数组进行排序，并迭代列表，从相应位置的数组重置每个元素。这避免了在原地尝试对链表进行排序会导致n2 log(n)性能的问题。

- Marcelo

---

请注意，“Arrays.sort(Object[])”也使用归并排序。如果您能在翻译中巧妙地提及此点，我可以删除我的回答。 - Bart Kiers

Answer 2

Arrays.sort(int[] a) 使用经过调整的快速排序算法。

Arrays.sort(Object[] a) 使用修改过的归并排序算法。

- Qwerky

Answer 3

通常情况下，您不能选择排序方式（无论使用内置的排序还是其他方式）。Collections 类提供了一个 sort 方法，对于大多数需求来说足够高效。

- Jim