java - Java链表插入排序

Question

我正在尝试为 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。我不要求完整的解决方案，只是一些指示。

Answer 1

首先，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) 操作。由于每次 insert 调用都会调用 get(i) O(M) 次，因此调用 O(M^2) 和排序 O(N^3)。

在“HERE #3”处，add(i,e) 重复之前的 get(i) 调用的列表遍历。但这还不错，因为每次 insert 调用只执行一次 add(i,e) 调用。所以整体复杂度不受影响。

在“HERE #4”处，add() 操作可以是 O(1) 或 O(M)，具体取决于它的实现方式。 (对于LinkedList.add()，它是O(1)，因为列表数据结构保留对列表最后一个节点的引用。)无论哪种方式，整体复杂性都不会受到影响。

简而言之:

• #2 处的代码肯定使其成为 O(N^3) 排序。

• #1 处的代码也可以使其成为 O(N^3) ...但不能使用标准 LinkedList 类。

<小时/>

那该怎么办？

• 一种方法是重新编码 insert 操作，以便它直接使用 next 和 prev 字段等遍历列表。不应调用任何“更高级别”列表操作:size、get(i)、add(e) 或 add(i, e)。

  但是，如果您通过扩展或包装 LinkedList 来实现此目的，则这不是一个选项。这些字段是私有(private)的。

• 如果您要扩展或包装 LinkedList，那么解决方案是使用 listIterator() 方法为您提供一个 ListIterator，并使用它进行高效遍历。 ListIterator 上的 add 操作是 O(1)。

• 如果(假设)您正在寻找对(大型)LinkedList 进行排序的最快方法，那么解决方案是使用 Collections.sort。在幕后，该方法将列表内容复制到数组中，对数组进行 O(NlogN) 排序，并根据排序后的数组重建列表。