Java 6提供哪些不同的排序算法？ [英] What different sorting algorithms are available in Java 6?

问题描述

计算机科学教科书中经常讨论诸如插入排序，选择排序，气泡排序等几种排序算法。给定一个整数或对象数组，是否有内置的Java 6语言API可以让我选择应用特定的排序算法对数组进行排序，而无需再次发明这些轮子？如果未内置于Java 6中，是否存在提供该功能的开源库？它们是什么？

The are several sorting algorithms like inserstion sort, selection sort, bubble sort etc. that are often discussed in computer science textbooks. Given an array of integers or objects, are there built-in Java 6 language API that let me choose to apply a specfic sort algorithm to sort the array instead of me reinventing these wheels again? If not built into Java 6, are there open source libraries that prodivde this functionality and what are they?

推荐答案

Arrays.sort （） 方法在所有原始类型数组中使用快速排序。

The Arrays.sort() methods use a quick sort in all primitive type arrays.

排序算法是一种经过优化的快速排序方法，改编自Jon L. Bentley和M. Douglas McIlroy的工程设计排序功能，《软件实践和经验》，第1卷。 23（11）P.1249-1265（1993年11月）。该算法可在许多数据集上提供n * log（n）性能，从而导致其他快速排序降低到二次性能。

The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

href = http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#sort(java.util.List） rel = noreferrer> Collections.sort（） 方法使用合并排序。 Arrays.sort（Object []） 和 Arrays.sort（T []，Comparator< ;? super T> ）。

The Collections.sort() method uses a merge sort. This sort is also used in Arrays.sort(Object[]) and Arrays.sort(T[], Comparator<? super T>).

排序算法是一种修改的mergesort（如果合并中的最高元素，则忽略合并低子列表小于高子列表中的最低元素）。该算法提供了有保证的n log（n）性能。此实现将指定的列表转储到数组中，对数组进行排序，然后遍历列表，从数组中的相应位置重置每个元素。这样可以避免由于尝试对链表进行排序而导致的n2 log（n）性能。

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.

这篇关于Java 6提供哪些不同的排序算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！