logo标签列表

Collections 和 Arrays 在 sort() 方面的区别

java
37

Collections和Arrays在sort()方法方面有什么区别？我知道Arrays的sort()使用二分查找进行排序，那Collections呢？如何选择使用哪一个呢？

15
二分查找并不是一种排序算法。 - SigmaX
8个回答
73

除了作用于不同类型的对象（Collections.sort 作用于 List，而 Arrays.sort 作用于数组），java.util.Collections.sort() 简单地调用 java.util.Arrays.sort() 来进行重要的操作。

此外，值得注意的是，Arrays.sort 使用归并排序算法。

4
原始数组的排序使用快速排序，因为对于原始数据来说，稳定性属性既不需要也没有意义。 - Paŭlo Ebermann
5
看起来这是Java 7中使用的timsort（修改版的归并排序）。https://dev59.com/o2865IYBdhLWcg3wCqBA - rogerdpack
19

Collections.sort() 操作的是 List，而 Arrays.sort() 操作的是数组。

Arrays.sort() 对基本类型数组使用 双轴快速排序算法，对对象数组使用 归并排序算法 进行排序。

Collections.sort() 的示例：

 ArrayList<Integer> arr = new ArrayList<Integer>();
 arr.add(15);
 arr.add(10);
 arr.add(5); 
 arr.add(2); 

 Collections.sort(arr);

Arrays.sort()的示例：

int[] arr = new int[4]
 arr[0]=15;
 arr[1]=10;
 arr[2]=5; 
 arr[3]=2; 

 Arrays.sort(arr);
13

我知道数组的sort()方法使用二分查找进行排序。

不，你并不知道这个。它并不是这样实现的。请参考Javadoc文档。

这个说法甚至没有意义。你不能“使用二分查找进行排序”。只有当数据已经排序时，二分查找才有效。也许你看到的是Arrays.binarySearch()假定数据已经排好序。

2
如果你正在处理数组，使用Arrays.sort()。如果你正在处理实现了集合接口的内容（例如ArrayList），则使用Collections.sort()。
1

当你处理列表时，使用Collection.sort；当处理数组时，使用Arrays.sort。但是，内部Collection.sort方法只使用了Arrays.sort方法。 现在，基于Timosrt技术而不是归并排序来进行内部排序，因为稳定、自适应的数组在归并排序中需要O(nlogn)次比较，但在Timsort最坏情况下也只需要O(nlogn)次比较，在最坏情况下需要n/2的存储空间，但这不是归并排序技术的情况。

1

就像其他答案所说的那样，当处理实现 Collection 接口的对象时，应使用 Collections.sort()；而当处理数组时，则应使用 Arrays.sort() 方法。

一个相关的问题是，如果要对一组值进行排序，哪种类型的数据结构更好。如果需要使用 List，则建议使用 LinkedList，因为插入操作的时间复杂度为 O(1)，而 ArrayList 则为 O(n)。

您还可以选择使用 SortedSet，如果不会有重复值或者希望避免出现重复值的情况。这样您就不必烦恼使用外部排序算法了。

如果你在排序，数组绝对比链表更胜一筹，并且声称“ArrayList将是O(n)”是错误的。 - user207421
1

数组类

public static void sort(T[] a)

参数：
a - 要排序的数组

实现说明（截断）：

  1. 双轴快速排序可在许多数据集上提供O(n log(n))的性能。
  2. 比传统（单轴）快速排序实现更快。

集合类

public static <T extends Comparable<? super T>> void sort(List list)

参数：
list - 要排序的列表。

实现说明（截断）：

  1. 是一种归并排序，当输入数组部分排序时，需要远少于n lg(n)次比较，同时在输入数组随机排序时提供传统归并排序的性能。
  2. 如果输入数组几乎排序完成，则实现需要大约n次比较。
  3. 临时存储要求因接近排序的输入数组而变化，对于随机排序的输入数组，需要n/2个对象引用。

总结

  1. 它们基于不同类型的数据，一个是数组，另一个是列表。
  2. 当涉及时间复杂度时，它取决于数据是部分排序还是随机排序。
  3. 当涉及空间时，Arrays.sort需要恒定的时间，但Collections.sort可能需要多达n/2的空间。
0

Arrays.sort() 可以对连续内存位置中的对象数组进行排序。它适用于数组输入。

Collections.sort() 可以对连续和离散内存位置中的对象进行排序：即它可以处理 ArrayList 和 LinkedList。 Collections.sort() 内部将 List 转换为对象数组，并调用 Arrays.sort() 进行排序。它总是创建原始列表对象的额外副本。对于输入的 ArrayList，它创建额外的副本以维护原始数组的可变性。对于输入的 LinkedList，为了提高性能，会创建一个新的数组。

它总是创建原始列表对象的额外副本：不，它不会。它会创建一个新的数组，但不会复制对象。 - user207421
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接