我正在尝试为LinkedList写一个插入排序,我有一个有效的方法,但是它的运行速度非常慢。一个多小时即可添加和排序50,000个元素。
public void insert(Custom c)
{
int i = 0;
for (i = 0; i < list.size(); i++)
{
if(list.get(i).compareTo(c) > 0 )
{
list.add(i,c);
return;
}
}
list.add(c);
}
我知道我可以使用Collections.Sort,但是对于此分配,我需要编写自己的LinkedList。我并不是只需要一些提示就寻求完整的解决方案。
最佳答案
首先,List
上的插入排序将变慢(O(N^2)
)...不管您如何操作。但是您似乎已将其实现为O(N^3)
。
这是您的代码...,将被调用N次,以添加每个列表元素。
public void insert(Entry e)
{
int i = 0;
for (i = 0; i < list.size(); i++) // HERE #1
{
if(list.get(i).compareTo(e) > 0 ) // HERE #2
{
list.add(i,e); // HERE #3
return;
}
}
list.add(e); // HERE #4
}
在“ HERE#1”处,我们最多迭代M次,其中M为当前(部分)列表长度;即
O(M)
。这是插入排序中固有的。但是,根据实现size()
方法的方式,可能会将迭代转换为O(M^2)
操作序列。 (LinkedList.size()
方法仅返回size
变量的值。在这里没有问题。但是,如果size()
计算了元素...)在“ HERE#2”处,我们进行了获取和比较。比较(
compareTo(...)
)很便宜,但是对链表的get(i)
操作涉及从头开始遍历该列表。那是一个O(M)
操作。而且,由于您每次get(i)
调用都执行O(M)
调用insert
次,因此将进行调用O(M^2)
和排序O(N^3)
。在“ HERE#3”处,
add(i,e)
重复上一个get(i)
调用的列表遍历。但这还不错,因为每个add(i,e)
调用只执行一次该insert
调用。因此,总体复杂性不受影响。在“ HERE#4”处,
add()
操作可以是O(1)
或O(M)
,具体取决于实现方式。 (对于LinkedList.add()
,它是O(1)
,因为列表数据结构保留对列表最后一个节点的引用。)两种方式都不会影响总体复杂性。简而言之:
#2处的代码肯定使它成为
O(N^3)
排序。#1处的代码也可以将其设置为
O(N^3)
...,但不能将其与标准LinkedList
类一起使用。那么该怎么办?
一种方法是重新编码
insert
操作,以便它直接使用next
和prev
字段等遍历列表。不应调用任何“更高级别”的列表操作:大小,get(i),add(e)或add(i,e)。但是,如果要通过扩展或包装
LinkedList
来实现此目的,则不是一种选择。这些字段是私有的。如果要扩展或包装
LinkedList
,则解决方案是使用listIterator()
方法为您提供ListIterator
,并将其用于有效遍历。 add
上的ListIterator
操作是O(1)
。如果(假设)您正在寻找对(大)
LinkedList
进行排序的最快方法,那么解决方案是使用Collections.sort
。在幕后,该方法将列表内容复制到数组,对该数组进行O(NlogN)
排序,然后从排序后的数组重构列表。