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

sorting a doubly linked list with merge sort

提问by user329820

I have found this code in the internet and it was for arrays ,I want to change it for doubly linked list(instead of index we should use pointer) would you please help me that how can i change merge method(I have changed sort method by myself) also this is not my home work ,I love working with linked list!!

我在互联网上找到了这段代码，它是用于数组的，我想将其更改为双向链表（而不是索引，我们应该使用指针）请您帮助我如何更改合并方法（我已更改排序方法）我自己）这也不是我的家庭作业，我喜欢使用链表！！

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++;
    }
}
}

回答by jasonmp85

Merge sort requires splitting the list quite often. Isn't iterating to the middle of a LinkedList pretty much the most expensive operation you can perform on it (well, short of sorting it)? I could see the merge step working pretty well (you're iterating forwards over two linked lists), but I'm not sure that this implementation is worth the trouble without an O(1)split operation.

合并排序需要经常拆分列表。迭代到 LinkedList 的中间不是您可以对其执行的最昂贵的操作（好吧，没有对其进行排序）？我可以看到合并步骤工作得很好（您在两个链表上向前迭代），但我不确定如果没有O(1)拆分操作，这个实现是否值得麻烦。

Followup

跟进

As pointed out to me, the O(n)split operation doesn't really add much to complexity when you're already doing O(n)things during the merge phase. Nevertheless, you're still going to run into trouble doing iteration like you're doing (not using an Iteratorbut instead using geton a Listwith poor random-access characteristics).

正如我所指出的，当您在合并阶段已经在做O(n) 的事情时，O(n)拆分操作并没有真正增加复杂性。尽管如此，你还是会喜欢你这样做碰到麻烦做迭代（不使用，而是使用一个差随机访问特性）。IteratorgetList

I was bored while debugging some other issue so wrote you what I consider to be a decent Java implementation of this algorithm. I followed Wikipedia's pseudocode verbatim and sprinkled in some generics and print statements. If you have any questions or concerns, just ask.

我在调试其他一些问题时很无聊，所以给你写了我认为是这个算法的一个体面的 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();
    }
}

To Run

跑步

1. Save the code to a file named MergeSort.java
2. Run javac MergeSort.java
3. Run java MergeSort
4. Marvel
5. Optionally, run javadoc -private MergeSort.javato create the documentation. Open the index.html file it creates.

1. 将代码保存到名为 MergeSort.java 的文件中
2. 跑 javac MergeSort.java
3. 跑 java MergeSort
4. 奇迹
5. （可选）运行javadoc -private MergeSort.java以创建文档。打开它创建的 index.html 文件。

回答by Péter T?r?k

It depends on what DoublyLinkedListis - is it a concrete user-defined type, or just an alias name for a linked list type?

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

In the first case, you should have indexed get/set methods and/or an iterator defined in it, which make the task simple.

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

In the latter case, why not use the standard java.util.LinkedList?

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

In terms of the Listinterface, the operation could be implemented like this:

在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());
    }
  }
}

This implementation is a bit more tedious than it would be with arrays, mostly since iterators are "consumed" by the nextoperation, so one must keep account of the current item in each list. With get, the code would be simpler, quite similar to the array solution, however it would be way slower for big lists, as @sepp2k pointed out.

这种实现比使用数组更乏味，主要是因为迭代器被操作“消耗” next，因此必须记录每个列表中的当前项目。使用get，代码会更简单，与数组解决方案非常相似，但是正如@sepp2k 指出的那样，对于大列表，它会更慢。

A couple more notes:

还有一些注意事项：

• the Java tradition is to use lowercase variable names, hence localDoublyLinkedList
• Java has no pointers, only references.

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

回答by lanoxx

I came across this problem yesterday. Here are some thoughts.

我昨天遇到了这个问题。这里有一些想法。

Sorting a DoublyLinkedListis different from sorting an Arrayas you can notmake index based references to any arbitrary item in the List. Instead you need to remember the items during each recursive step and then pass them on to the merge function. For each recursion step you only need to remember the first item of each list half. If you do not remember these items you will quickly end up with indexes, but this leads you to the problem that in your merge-function you need to traverse the whole list with for-loops to find the items to merge. That in turn means you get a complexity of O(n^2).

排序 aDoublyLinkedList与排序 an 不同，Array因为您不能对列表中的任何任意项目进行基于索引的引用。相反，您需要记住每个递归步骤中的项目，然后将它们传递给合并函数。对于每个递归步骤，您只需要记住每个列表一半的第一项。如果您不记得这些项目，您很快就会得到索引，但这会导致问题，在您的merge-function 中，您需要使用for-loops遍历整个列表以找到要合并的项目。这反过来意味着您将获得O(n^2).

Another important point is the step of recursing into the list and dividing the list in two halves. You can do this step in the recursive part by using for-loops. Contrary to the merge-part at this step the for-loops will only yield a complexity of O(log(n) * n/2)and this is still below the overall O(n*log(n))complexity. Here is why:

另一个重要的点是递归到列表中并将列表分成两半的步骤。您可以使用for-loops在递归部分执行此步骤。与merge此步骤中的 -for部分相反， -循环只会产生 的复杂度，O(log(n) * n/2)并且这仍然低于整体O(n*log(n))复杂度。原因如下：

1. You always need to find the first item of each half of list part.

2. In the first recursion step you need to pass the firstitem and the item at position n/2. This takes n/2steps to find.

3. In each following step you need to find the middle item for each of the two halves of the list which gives us n/4to find the item in the first halve and n/4in the other halve. In total thats n/2.

4. In each following recursive step the amount of list parts double and the lengths is divided by two:

   • 4 * n/8in the 3rd recursion depth

   • 8 * n/16in the 4th recursion depth, and so on...

5. The recursion depth is log(n)and in each step we perform n/2steps. This equals O(log(n)*n/2)

1. 您总是需要找到列表部分每一半的第一项。

2. 在第一个递归步骤中，您需要传递firstitem 和 position 处的 item n/2。这需要n/2步骤才能找到。

3. 在接下来的每个步骤中，您需要为列表的两半中的每一半找到中间项目，这使我们n/4能够在前半部分和另一半中找到项目n/4。总而言之n/2。

4. 在接下来的每个递归步骤中，列表部分的数量加倍，长度除以二：

   • 4 * n/8在第三个递归深度

   • 8 * n/16在第四个递归深度，依此类推...

5. 递归深度是，log(n)并且在每一步中我们执行n/2步骤。这等于O(log(n)*n/2)

Finally here is some code:

最后是一些代码：

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

mergeSort:

归并排序：

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;
    }
}

and merge:

并合并：

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
}

The maximum amount of memory used is also pretty low (not including the list itself). Correct me if I'm wrong but it should be less than 400 bytes (on 32bit). It would be 12 byte per call on mergeSort times the recursion depth of log(n) plus 20 bytes for the variables of merge thus: 12*log(n)+20 bytes.

使用的最大内存量也很低（不包括列表本身）。如果我错了，请纠正我，但它应该少于 400 个字节（在 32 位上）。每次调用 mergeSort 将是 12 字节乘以 log(n) 的递归深度加上 20 字节的合并变量，因此：12*log(n)+20 字节。

P.S. Code tested on 1 million items (takes 1200ms). Also DoublyLinkedListis a container that stores the first ListElementof the list.

PS Code 测试了 100 万个项目（需要 1200 毫秒）。也是DoublyLinkedList一个容器，用于存储ListElement列表的第一个。

Update:I have answered a similar question about Quicksortusing the same data structures, however in comparison to this Mergesort implementation it runs much slower. Here are some updated timings for reference:

更新：我已经使用相同的数据结构回答了有关Quicksort的类似问题，但是与此 Mergesort 实现相比，它运行速度要慢得多。以下是一些更新的时间供参考：

Mergesort:

归并排序：

1.000.000 Items:  466ms
8.300.000 Items: 5144ms

Quicksort:

快速排序：

1.000.000 Items:  696ms  
8.300.000 Items: 8131ms

Note the timings are specific to my hardware and you might get different results.

请注意，计时特定于我的硬件，您可能会得到不同的结果。

回答by gwohpq9

First of all, you must NOT use indexes when dealing with linked lists. Do it like this:

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

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

And for merging

并为合并

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()) );
}

This way it will still be O(n log n)

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

回答by George

Another idea is to create an array with all the elements of the list, sort the array and then insert the elements to the list again.

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

Pro: very simple to implement, faster if poor implementation of list mergesort (maybe also faster than good implementations)

优点：实施起来非常简单，如果列表合并排序的实施不佳，则速度更快（可能也比好的实施更快）

Contra: uses some extra space (O(n))

反对：使用一些额外的空间（O（n））