用归并排序对双链表排序

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

5 个解决方案

#1

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 Iterator but instead using get on a List with poor random-access characteristics).

正如我所指出的，在合并阶段，O(n)拆分操作并不能真正增加复杂度。尽管如此，在进行迭代时仍然会遇到麻烦(不是使用迭代器，而是使用具有糟糕的随机访问特性的列表上的get)。

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. 将代码保存到名为mergesor .java的文件中
3. Run javac MergeSort.java
4. 运行javac MergeSort.java
5. Run java MergeSort
6. 运行java归并排序
7. Marvel
8. 奇迹
9. Optionally, run javadoc -private MergeSort.java to create the documentation. Open the index.html file it creates.
10. 可选地，运行javadoc -private MergeSort。创建文档的java。打开索引。它创建的html文件。

#2

It depends on what DoublyLinkedList is - 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 List interface, 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 next operation, 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.

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

A couple more notes:

一些注意事项:

• the Java tradition is to use lowercase variable names, hence localDoublyLinkedList
• Java的传统是使用小写的变量名，因此使用localDoublyLinkedList
• Java has no pointers, only references.
• Java没有指针，只有引用。

#3

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

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

Sorting a DoublyLinkedList is different from sorting an Array as you can not make 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).

对DoublyLinkedList进行排序与对数组进行排序不同，因为不能对列表中的任意项进行基于索引的引用。相反，您需要在每个递归步骤中记住条目，然后将它们传递给merge函数。对于每个递归步骤，您只需要记住每个列表的第一部分。如果您不记得这些项，您将很快得到索引，但是这会导致您在您的合并函数中需要使用for循环遍历整个列表，以找到要合并的项。这反过来又意味着你得到一个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循环在递归部分中执行此步骤。与此步骤的合并部分相反，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 first item and the item at position n/2. This takes n/2 steps to find.

   在第一个递归步骤中，需要传递第一个项和位置为n/2的项。这需要n/2步才能找到。

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/4 to find the item in the first halve and n/4 in the other halve. In total thats n/2.

   在接下来的每一步中，你需要为列表的两个部分找到中间的项，这两个部分给了我们n/4来找到第一个一半的项和另一个一半的n/4。总n / 2。

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

   在每一个递归步骤中，列表部分的数量加倍，长度除以2:

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

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

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

     8 * n/16在第4递归深度，等等…

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

   递归深度为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位)。合并排序每次调用12字节，乘以log(n)的递归深度，加上归并变量的20字节，即12*log(n)+20字节。

P.S. Code tested on 1 million items (takes 1200ms). Also DoublyLinkedList is a container that stores the first ListElement of the list.

在100万件物品上测试P.S.代码(需要1200ms)。DoublyLinkedList也是一个容器，它存储列表的第一个ListElement。

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

更新:我已经回答了使用相同数据结构的快速排序的类似问题，但是与此合并排序实现相比，它运行得要慢得多。以下是一些更新后的参考时间:

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.

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

#4

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)

#5

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)

Pro:实现起来非常简单，如果列表合并排序的糟糕实现会更快(可能也比好的实现要快)

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

Contra:使用一些额外的空间(O(n))