我突然想到了一个问题，因为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] 删除。
我来说两句