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

Question

有几种排序算法,如计算机科学教科书中经常讨论的插入排序,选择排序,冒泡排序等.给定一个整数或对象数组,是否有内置的Java 6语言API,让我选择应用特定的排序算法来排序数组,而不是重新重新发明这些轮子？如果没有内置到Java 6中,是否有开源库可以生成这个功能,它们是什么？

Answer 1

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

排序算法是一个经过调整的快速排序,改编自Jon L. Bentley和M. Douglas McIlroy的"工程排序功能",软件实践和经验,卷.23(11)P.1249-1265(1993年11月).该算法在许多数据集上提供n*log(n)性能,导致其他快速降序降级为二次性能.

该Collections.sort()方法使用合并排序.这种类型也用于Arrays.sort(Object[])和Arrays.sort(T[], Comparator<? super T>).

排序算法是修改后的mergesort(如果低子列表中的最高元素小于高子列表中的最低元素,则省略合并).该算法提供有保证的n log(n)性能.此实现将指定的列表转储到数组中,对数组进行排序,并迭代列表,从数组中的相应位置重置每个元素.这样可以避免尝试对链接列表进行排序所导致的n2 log(n)性能.

Answer 2

Arrays.sort(int[] a) 使用调整的快速排序.

Arrays.sort[Object[] a) 使用修改后的mergesort.