Arrays和Collections 对于sort的不同实现原理

时间:2024-10-06 18:37:02

详见:http://blog.yemou.net/article/query/info/tytfjhfascvhzxcytp46

1、Arrays.sort()

该算法是一个经过调优的快速排序,此算法在很多数据集上提供N*log(N)的性能,这导致其他快速排序会降低二次型性能。

2、Collections.sort()

该算法是一个经过修改的合并排序算法(其中,如果低子列表中的最高元素效益高子列表中的最低元素,则忽略合并)。此算法可提供保证的N*log(N)的性能,此实现将指定列表转储到一个数组中,然后再对数组进行排序,在重置数组中相应位置处每个元素的列表上进行迭代。这避免了由于试图原地对链接列表进行排序而产生的n2 log(n)性能。