我正在尝试为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操作,以便它直接使用nextprev字段等遍历列表。不应调用任何“更高级别”的列表操作:大小,get(i),add(e)或add(i,e)。

但是,如果要通过扩展或包装LinkedList来实现此目的,则不是一种选择。这些字段是私有的。
如果要扩展或包装LinkedList,则解决方案是使用listIterator()方法为您提供ListIterator,并将其用于有效遍历。 add上的ListIterator操作是O(1)
如果(假设)您正在寻找对(大)LinkedList进行排序的最快方法,那么解决方案是使用Collections.sort。在幕后,该方法将列表内容复制到数组,对该数组进行O(NlogN)排序,然后从排序后的数组重构列表。

10-07 19:33
查看更多