我突然想到了一个问题,因为get(index)
linkedList方法的时间复杂度不是O(1),而是O(N),那么,这会影响排序的时间复杂度吗?例如,下面的代码(冒泡排序):
public static void bubbleSort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
在执行冒泡排序时,我需要获取元素。在任何排序算法中,都需要获取元素,因此...执行气泡排序时,是否需要平均时间复杂度O(n * log(n)* n)?如果是,当我使用时Collections.sort(linkedList)
,平均时间复杂度是否也为O(n * log(n)* n)?
这是List.sort
(Java 13)的实现
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
如您所见,要排序的列表实现并不重要,其性能几乎相同。
现在,如果我们看一下如何toArray
实现,我们将看到以下内容:
链表
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
数组列表
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
因此,如果您想对LinkedList进行排序,它将比ArrayList慢一点,但幅度不大。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句