相关疑难解决方法(0)

我们知道快速排序是最快的排序算法.

collections.sort使用合并排序算法而不是快速排序.但是Arrays.sort使用快速排序.

Collections.sort使用合并排序而不是快速排序的原因是什么？

我使用的是JDK-8(x64).对于Arrays.sort(primitives),我在Java文档中找到了以下内容:

该排序算法是一个双枢轴快速排序弗拉基米尔·Yaroslavskiy,乔恩·本特利,以及约书亚Bloch.`

对于Collections.sort(对象),我发现了这个"Timsort":

这个实现是一个稳定的,自适应的,迭代的mergesort ......这个实现将指定的列表转储到一个数组中,对数组进行排序,并迭代列表,从数组中的相应位置重置每个元素.

如果Collections.sort使用数组,为什么不调用Arrays.sort或使用双枢轴QuickSort？为什么要使用Mergesort？

我找不到Java 7的文档,我只能找到关于Java 6的文档,它仍然可以快速或合并.有谁知道如何Arrays.sort在Java 7中找到该方法的文档？

为什么？它更快还是更有效？

对于具有一个核心的系统,我们可以使用quicksort.我们应该在具有两个内核,四个内核或八个内核的系统上使用什么？

以下引用来自Wikipedia Merge Sort页面中的"与其他排序算法的比较"部分

在典型的现代体系结构中,高效的快速排序实现通常优于mergesort,用于排序基于RAM的阵列.[citation needed]另一方面,合并排序是一种稳定的排序,在处理慢速访问顺序介质方面更有效.

我的问题:

1. 当要排序的数据全部适合内存时,为什么Quicksort的性能优于Mergesort？如果所需的所有数据都被缓存,或者内存中的Quicksort和Mergesort都不能快速访问？

2. 为什么Mergesort在处理缓慢访问的顺序数据方面更有效率(例如在要排序的数据不能全部适合内存的情况下从磁盘中)？

3. (从下面的评论转到此处)在arrn个元素的基元数组(数据是顺序的)中.必须在MergeSort中读取和比较的元素对是arr[0]和arr[n/2](在最终合并中发生).现在认为被读取并在快速排序相比是一对具有元件arr[1]和arr[n](在第一分区中发生时,假设我们交换与第一元件的随机选择的枢轴).我们知道数据是以块的形式读取并加载到缓存中,或者加载到磁盘到内存(如果我错了,请纠正我)那么使用MergeSort时所需的数据是否更有可能在一个块中加载？在我看来,MergeSort总是会有优势,因为它可能会比较更紧密的元素.我知道这是假的(见下图),因为QuickSort显然更快......我知道MergeSort不到位并需要额外的内存,这可能会减慢速度.除了我在分析中遗漏了哪些东西？

图像来自Princeton CS MergeSort和QuickSort幻灯片

我的动机:

我想理解上面这些概念,因为它们是为什么在排序LinkedList时首选mergeSort的主要原因之一,或者在排序数组或顺序数据时没有优先顺序数据和quickSort.为什么mergeSort用于在Java中对Object进行排序,而quickSort用于在java中对原始类型进行排序.

更新:Java 7 API实际上使用TimSort对Object进行排序,Object是MergeSort和InsertionSort的混合体.对于原语Dual-Pivot QuickSort.这些更改是从Java SE 7开始实现的.这与排序算法的稳定性有关.为什么Java的Arrays.sort方法对不同类型使用两种不同的排序算法？

编辑:

我将感谢一个解决以下方面的答案:

• 我知道两种排序算法在移动,读取和比较的数量上有所不同.如果那些原因导致了我在我的问题中列出的行为(我怀疑它),那么彻底解释排序算法的步骤和过程如何导致从磁盘或内存中寻找数据的优点或缺点将非常感激.
• 欢迎举例.我通过例子更好地学习.

注意:如果你正在阅读@ rcgldr的答案.看看我们在聊天室里的对话,它有很多很好的解释和细节.https://chat.stackoverflow.com/rooms/161554/discussion-between-rcgldr-and-oliver-koo

可能重复:
为什么java Arrays对不同类型使用两种不同的排序算法？

所以我正在阅读各种排序实现的Arrays 文档.我注意到的是,一些实现使用了调整的快速排序,而其他实现使用了修改后的mergesort.为什么会出现差异？

谢谢!

维基百科关于AVL树的文章的第三段说:"由于AVL树更加严格平衡,因此对于查找密集型应用程序来说,它们比红黑树更快."

因此,不应该使用AVL树而不是红黑树来实现TreeMap(因为基于散列的数据结构会有更多的查找密集型应用程序)？

根据维基百科:

"在Java中,Arrays.sort()方法根据数据类型使用合并排序或调整快速排序,并且当正在排序的数组元素少于7个时,实现效率切换到插入排序"

但为什么？合并排序和快速排序都是O(n log n).

我知道Java的Arrays.sort方法使用MergeSort来排序对象(或对象集合)的数组,因为它是稳定的,而Java使用QuickSort作为基元数组,因为我们不需要稳定性,因为两个相等的整数是无法区分的,即它们的身份不是'无所谓.

我的问题是,在原语的情况下,为什么Java不使用MergeSort的保证O(n log n)时间而是使用QuickSort的平均O(n log n)时间？在这里的一个相关答案的最后一段中,解释说:

对于引用类型,引用对象通常占用的内存比引用数组多得多,这通常无关紧要.但对于原始类型,克隆数组会使内存使用量翻倍.

这是什么意思？克隆引用仍然至少与克隆基元一样昂贵.在基元数组上使用QuickSort(平均O(n log n))而不是MergeSort(保证O(n log n)时间)还有其他原因吗？

我正在制作一个带有滚动视图的2D游戏(想想Red Alert或Zelda),但我正在绘制图纸.

基本上,地图上绘制了两种类型的对象.有些人有固定的位置(如树木和建筑物),有些则有移动(玩家,敌人,飞行箭头).

要使事物以正确的方式出现在彼此前面,需要按特定顺序绘制(首先是远处的物体并朝向"相机"工作).

现在我每次游戏更新(每秒100次)时都会对所有对象(两种)的列表进行排序,这感觉就像浪费了大量的CPU时间.对象的顺序很少变化,当它们发生时,它们通常只在列表中向上或向下移动一个位置.

另一个问题是只需要考虑实际在屏幕上的对象.由于地图可能变得非常大,有1000个物体,我不想每秒100次对它们进行排序.

你怎么建议我解决这个问题？