使用归并排序对双向链表进行排序。

Question

使用归并排序对双向链表进行排序。

javaalgorithmsortinglinked-listmergesort

10

我从互联网上找到了这段代码，它是用于数组的。现在我想将其改为适用于双向链表(我们应该使用指针而不是索引)，你能帮我看看如何更改合并方法吗？（我已经自己改变了排序方法）同时声明一下，这不是我的作业，我只是喜欢使用链表！！

public class MergeSort {

private DoublyLinkedList LocalDoublyLinkedList;

public MergeSort(DoublyLinkedList list) {
    LocalDoublyLinkedList = list;

}

public void sort() {

    if (LocalDoublyLinkedList.size() <= 1) {
        return;
    }
    DoublyLinkedList listOne = new DoublyLinkedList();
    DoublyLinkedList listTwo = new DoublyLinkedList();
    for (int x = 0; x < (LocalDoublyLinkedList.size() / 2); x++) {
        listOne.add(x, LocalDoublyLinkedList.getValue(x));
}
for (int x = (LocalDoublyLinkedList.size() / 2) + 1; x < LocalDoublyLinkedList.size`(); x++) {`
    listTwo.add(x, LocalDoublyLinkedList.getValue(x));
}
//Split the DoublyLinkedList again
    MergeSort sort1 = new MergeSort(listOne);
    MergeSort sort2 = new MergeSort(listTwo);
    sort1.sort();
    sort2.sort();

    merge(listOne, listTwo);
}

private void merge(DoublyLinkedList a, DoublyLinkedList b) {
    int x = 0;
    int y = 0;
    int z = 0;
    while (x < first.length && y < second.length) {
        if (first[x] < second[y]) {
            a[z] = first[x];
            x++;
        } else {
            a[z] = second[y];
            y++;
        }
        z++;
    }
//copy remaining elements to the tail of a[];
    for (int i = x; i < first.length; i++) {
        a[z] = first[i];
        z++;
    }
    for (int i = y; i < second.length; i++) {
        a[z] = second[i];
        z++;
    }
}
}

- user329820

5个回答

3

我昨天遇到了这个问题，以下是我的一些想法。

对于排序一个 DoublyLinkedList 而言，与排序一个 Array 不同，因为你不能基于索引引用列表中的任意项。相反，你需要在每个递归步骤中记住项目，然后将它们传递给合并函数。对于每个递归步骤，你只需要记住每个列表半部分的第一项。如果你不记得这些项，你很快就会遇到索引问题，但这会导致在你的 merge 函数中需要使用 for 循环遍历整个列表以查找要合并的项。反过来，这意味着你会得到一个复杂度为 O(n^2)。

另一个重要的点是递归进入列表并将列表分成两半的步骤。你可以通过使用 for 循环在递归部分完成此步骤。与 merge 部分相反，在此步骤中，for 循环仅产生 O(log(n) * n/2) 的复杂度，这仍然低于总的 O(n*log(n)) 复杂度。原因在于：

您总是需要找到列表部分的每一半中的第一个项目。
在第一次递归步骤中，您需要传递first项和位置n/2处的项。这需要n/2步来查找。
在每个后续步骤中，您需要找到列表的两个半部分的中间项，这给我们n/4在第一半中找到该项，在另一半中找到n/4。总共是n/2。
在每个后续递归步骤中，列表部件数量加倍，长度除以二：
- 在第三个递归深度中为4 * n/8
- 在第四个递归深度中为8 * n/16，依此类推...
递归深度为log(n)，在每个步骤中我们执行n/2步。这等于O(log(n)*n/2)

最后是一些代码:

public DoublyLinkedList mergesort(DoublyLinkedList in, int numOfElements) {
    in.first = mergesort(in.first, numOfElements);      
    return in;
}

归并排序：

public ListElement mergesort(ListElement first, int length) {
    if(length > 1) {
        ListElement second = first;
        for(int i=0; i<length/2; i++) {
            second = second.next;
        }
        first = mergesort(first, length/2);
        second = mergesort(second, (length+1)/2);
        return merge(first, second, length);
    } else {
        return first;
    }
}

并入：

public ListElement merge(ListElement first, ListElement second, int length) {
    ListElement result = first.prev; //remember the beginning of the new list will begin after its merged
    int right = 0;
    for(int i=0; i<length; i++) {
        if(first.getKey() <= second.getKey()) {
            if(first.next == second) break; //end of first list and all items in the second list are already sorted, thus break
            first = first.next;
        } else {
            if(right==(length+1)/2) 
                break; //we have merged all elements of the right list into the first list, thus break
            if(second == result) result = result.prev; //special case that we are mergin the last element then the result element moves one step back.
            ListElement nextSecond = second.next;
            //remove second
            second.prev.next = second.next;
            second.next.prev = second.prev;
            //insert second behind first.prev
            second.prev = first.prev;
            first.prev.next = second;
            //insert second before first
            second.next = first; 
            first.prev = second;
            //move on to the next item in the second list
            second = nextSecond;
            right++;
        }
    }
    return result.next; //return the beginning of the merged list
}

最大使用的内存空间也很低（不包括列表本身）。如果我没记错，它应该小于400字节（在32位上）。每次合并排序调用的占用空间是12个字节乘以log(n) 的递归深度，再加上merge变量的20个字节，因此总共占用空间为：12*log(n)+20字节。

注：代码已在100万项上进行测试（需要1200毫秒）。DoublyLinkedList是一个存储列表第一个ListElement的容器。

更新：我回答了一个类似的问题Quicksort，使用相同的数据结构，但与这个Mergesort实现相比速度要慢得多。以下是一些更新后的时间参考：

Mergesort:

1.000.000 Items:  466ms
8.300.000 Items: 5144ms

快速排序:

1.000.000 Items:  696ms  
8.300.000 Items: 8131ms

请注意，计时是针对我的硬件进行的，您可能会得到不同的结果。

- lanoxx

3

这取决于 DoublyLinkedList 是什么 - 它是一个具体的用户定义类型，还是链表类型的别名名称？

在第一种情况下，您应该在其中定义了索引获取/设置方法和/或迭代器，这使得任务变得简单。

在后一种情况下，为什么不使用标准的 java.util.LinkedList？

就 List 接口而言，可以这样实现操作：

<T> List<T> merge(List<T> first, List<T> second, List<T> merged) {
  if (first.isEmpty())
    merged.adAll(second);
  else if (second.isEmpty())
    merged.adAll(first);
  else {
    Iterator<T> firstIter = first.iterator();
    Iterator<T> secondIter = second.iterator();
    T firstElem = firstIter.next();
    T secondElem = secondIter.next();

    do {
      if (firstElem < secondElem) {
        merged.add(firstElem);
        firstElem = firstIter.hasNext() ? firstIter.next() : null;
      } else {
        merged.add(secondElem);
        secondElem = secondIter.hasNext() ? secondIter.next() : null;
      }
    } while (firstIter.hasNext() && secondIter.hasNext());
    //copy remaining elements to the tail of merged
    if (firstElem != null)
      merged.add(firstElem);
    if (secondElem != null)
      merged.add(secondElem);
    while (firstIter.hasNext()) {
      merged.add(firstIter.next());
    }
    while (secondIter.hasNext()) {
      merged.add(secondIter.next());
    }
  }
}

这个实现比使用数组要繁琐一些，主要是因为迭代器被“消耗”了，所以必须在每个列表中跟踪当前项。使用get，代码会更简单，与数组解决方案非常相似，但对于大型列表来说速度会慢得多，正如@sepp2k指出的那样。

还有几点需要注意：

Java传统上使用小写变量名，因此使用localDoublyLinkedList
Java没有指针，只有引用。

- Péter Török

1

在没有提到链表的索引获取/设置方法是O(n)的情况下，提及它们似乎有些危险。编写排序算法时，绝对不应该使用get和set方法。 - sepp2k

1

首先，在处理链表时，绝不能使用索引。应该这样做：

while (i < in.size/2){
  listOne.addLast( in.remove(in.first()) );
  i++
}
while(!in.isEmptly){
  listTwo.addLast( in.remove(in.first()) );
}

而对于合并

merge(a, b, out){
  while(!a.empty && !b.empty){
    if(a.first() >= b.first())
      out.addLast( a.remove(a.first()) );
    else
     out.addLast( b.remove(b.first()) );

  //remember to take care of the remaining elements 
  while(!a.empty)
    out.addLast( a.remove(a.first()) );
  while(!b.empty)
    out.addLast( b.remove(b.first()) );
}

这样它仍然是O(n log n)

- gwohpq9

0

另一个想法是创建一个包含列表所有元素的数组，对该数组进行排序，然后再将元素插入到列表中。

优点：实现非常简单，如果列表归并排序的实现较差（也许比好的实现更快）。

缺点：使用了一些额外的空间（O(n)）。

- George

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jasonmp85 · Accepted Answer

归并排序需要经常分割列表。在LinkedList中迭代到中间位置几乎是你可以执行的最昂贵操作（好吧，除了对其进行排序）。我可以看到合并步骤非常有效（你正在两个链接列表上向前迭代），但是如果没有O（1）分割操作，我不确定这种实现是否值得麻烦。

后续

正如我所指出的那样，当您已经在合并阶段执行O（n）操作时，O（n）分割操作确实不会增加太多复杂性。尽管如此，您仍将遇到问题，因为您正在执行迭代操作（而不是使用Iterator而是在具有较差随机访问特性的List上使用get）。

我在调试其他问题时感到无聊，因此为您编写了一个我认为是不错的Java实现此算法。我严格按照维基百科的伪代码，并添加了一些泛型和打印语句。如果您有任何问题或疑虑，请随时提问。

import java.util.List;
import java.util.LinkedList;

/**
 * This class implements the mergesort operation, trying to stay
 * as close as possible to the implementation described on the
 * Wikipedia page for the algorithm. It is meant to work well
 * even on lists with non-constant random-access performance (i.e.
 * LinkedList), but assumes that {@code size()} and {@code get(0)}
 * are both constant-time.
 *
 * @author jasonmp85
 * @see <a href="http://en.wikipedia.org/wiki/Merge_sort">Merge sort</a>
 */
public class MergeSort {
    /**
     * Keeps track of the call depth for printing purposes
     */
    private static int depth = 0;

    /**
     * Creates a list of 10 random Longs and sorts it
     * using {@link #sort(List)}.
     *
     * Prints out the original list and the result.
     *
     */
    public static void main(String[] args) {
        LinkedList<Long> list = new LinkedList<Long>();

        for(int i = 0; i < 10; i++) {
            list.add((long)(Math.random() * 100));
        }

        System.out.println("ORIGINAL LIST\n" + 
                           "=================\n" +
                           list + "\n");

        List<Long> sorted = sort(list);

        System.out.println("\nFINAL LIST\n" +
                           "=================\n" +
                           sorted + "\n");
    }

    /**
     * Performs a merge sort of the items in {@code list} and returns a
     * new List.
     *
     * Does not make any calls to {@code List.get()} or {@code List.set()}.
     * 
     * Prints out the steps, indented based on call depth.
     *
     * @param list the list to sort
     */
    public static <T extends Comparable<T>> List<T> sort(List<T> list) {
        depth++;
        String tabs = getTabs();

        System.out.println(tabs + "Sorting: " + list);

        if(list.size() <= 1) {
            depth--;
            return list;
        }

        List<T> left   = new LinkedList<T>();
        List<T> right  = new LinkedList<T>();
        List<T> result = new LinkedList<T>();

        int middle = list.size() / 2;

        int added = 0;
        for(T item: list) {
            if(added++ < middle)
                left.add(item);
            else
                right.add(item);
        }

        left = sort(left);
        right = sort(right);

        result = merge(left, right);

        System.out.println(tabs + "Sorted to: " + result);

        depth--;
        return result;
    }

    /**
     * Performs the oh-so-important merge step. Merges {@code left}
     * and {@code right} into a new list, which is returned.
     *
     * @param left the left list
     * @param right the right list
     * @return a sorted version of the two lists' items
     */
    private static <T extends Comparable<T>> List<T> merge(List<T> left,
                                                           List<T> right) {
        String tabs = getTabs();
        System.out.println(tabs + "Merging: " + left + " & " + right);

        List<T> result = new LinkedList<T>();
        while(left.size() > 0 && right.size() > 0) {
            if(left.get(0).compareTo(right.get(0)) < 0)
                result.add(left.remove(0));
            else
                result.add(right.remove(0));
        }

        if(left.size() > 0)
            result.addAll(left);
        else
            result.addAll(right);

        return result;
    }

    /**
     * Returns a number of tabs based on the current call depth.
     *
     */
    private static String getTabs() {
        StringBuffer sb = new StringBuffer("");
        for(int i = 0; i < depth; i++)
            sb.append('\t');
        return sb.toString();
    }
}

运行

将代码保存到名为MergeSort.java的文件中
运行javac MergeSort.java
运行java MergeSort
惊叹不已
可选地，运行javadoc -private MergeSort.java以创建文档。打开它创建的index.html文件。