对于通用排序,答案似乎是否定的,因为快速排序,合并排序和堆排序往往在平均和最差情况下表现更好.但是,插入排序似乎在增量排序方面表现优异,即在保持列表排序的同时,在一段时间内一次向列表添加元素,尤其是在插入排序实现为链接列表时(O(log) n)平均情况与O(n)).但是,堆似乎能够(或几乎)执行增量排序(从堆中添加或删除单个元素具有O(log n)的最坏情况).那么插入排序与其他基于比较的排序算法或堆有什么关系呢？
我发现java.util.Arrays.sort(Object[])使用2种排序算法(在JDK 1.6中).
伪代码:
if(array.length<7)
insertionSort(array);
else
mergeSort(array);
为什么这里需要2种排序？为了效率？
我想在它们的产品按降序排列的有界正方形内生成成对的笛卡尔坐标.例如,对于大小为3的正方形,坐标为:
(3,3), (3,2), (2,3), (2,2), (3,1), (1,3), (2,1), (1,2), (1,1)
有没有办法快速生成这个列表 - 即一个将整数映射到第n个坐标的常量时间函数？
我正在处理文件中的整数列表。我必须使用排序算法按降序对它们进行分类。我熟悉一些排序算法的运行时间，并且我知道它们的使用是视情况而定的。所以我的问题是：对于已经 90% 排序的任何大小的列表，最快的排序算法是什么？（在我的文件中，我有 10.000 个条目，但其中 9.500 个已经排序）。
谢谢，