为什么Java impl选择合并排序而不是快速排序？为什么他们将内容复制到数组？
API:"排序算法是一个经过修改的mergesort(如果低子列表中的最高元素小于高子列表中的最低元素,则省略合并.)此算法提供有保证的n log(n)性能.将指定的列表转储到一个数组中,对数组进行排序,然后遍历列表,从数组中的相应位置重置每个元素.这样可以避免尝试对链接列表进行排序所导致的n2 log(n)性能. "
Java人员用平均情况交易了最坏情况,你可能知道,在最坏的情况下,快速排序可能会在O(n ^ 2)中运行.
你可以在API中读取,就地排序链表更复杂n ^ 2log(n)
合并排序是稳定的,对于快速排序的高效版本而言并非如此.(这对于排序对象非常重要+许多程序员在使用Collections.sort()时认为这是理所当然的)
文档给出了您的两个问题的答案:
该算法提供有保证的n log(n)性能.
合并排序没有快速排序的病态情况
合并排序比快速排序的另一个优点是合并排序稳定; 快速排序通常不稳定.(显然,经过足够的努力,你可以使它稳定,但我相信这样做相对昂贵.)
这样可以避免尝试对链接列表进行排序所导致的n 2 log(n)性能.
首先复制到数组意味着您不依赖于原始集合访问单个元素的复杂性.我想它可以查看列表是否实现RandomAccess并排序到位,如果是这样,但RandomAccess仅在1.4中引入.
| 归档时间： |
|
| 查看次数： |
2312 次 |
| 最近记录： |