Java 排序程序

Question

我正在尝试实现一个代码来对列表进行合并排序。有人告诉我使用 getFirst() 和 addAll() 但我不知道这是怎么想出来的：

此外，我不能将 void 用于 mergeSort 方法 - 因为它会给我一个错误，所以我必须 return 一些东西。

任何建议将不胜感激

Answer 1

虽然有一个公认的答案，但此代码使用 getFirst() 和 addAll()，如原始 post 中所述，我认为这是本练习的预期目的。它使用自下而上的合并排序，避免了自上而下的问题必须扫描列表以找到拆分列表的中点。

自下而上归并排序的基本概念是将两个 1 节点列表合并以创建一个排序的 2 节点列表，将两个排序的 2 节点列表合并以创建一个排序的 4 节点列表，两个排序的 4 节点列表是合并以创建一个排序的 8 节点列表，依此类推，类似于数组的自底向上合并排序。

自下而上的合并排序使用小型列表数组 (java)、指向节点的指针 (C) 或指向节点的迭代器 (C++) 来保存列表。对于此示例代码，我使用了一个包含 32 个列表的数组。对于数组的每个成员，该成员要么为 null，要么引用一个列表，其中 array[i] 的列表的节点数有 2^i 个节点：array[0] 1 个节点，array[1] 2 个节点，array [2] 4 个节点，...，数组 [30] 2^30 = 10 亿个节点。如果节点总数 >= 2^32（40 亿）个节点，则最后一个成员将拥有 2^31 = 20 亿个节点或更多。

每次从源列表的前面删除一个节点，源列表中的每个节点用于创建一个包含 1 个节点的列表 mm，然后将 mm 合并到数组，在遇到第一个 null 时停止：

    while(source_list not empty){
        mm = source_list.removeNode(()   // mm = next node from source list
        for(i = 0; i < 32; i++){         // merge mm into array
            if(array[i] != null){
                mm = merge(array[i], mm)
                array[i] = null
            } else {
                break
            }
        }
        if(i == 32)    // if i == 32, there is no array[32], so 
            i = 31     //  use array[31] instead
        array[i] = mm
    }

模式看起来像这样：

mm = next node from source list  // 1 node list
array[0] = mm

mm = next node from source list  // 1 node list
mm = merge(array[0], mm)         // 2 node list
array[0] = null
array[1] = mm

mm = next node from source list  // 1 node list
array[0] = mm

mm = next node from source list  // 1 node list
mm = merge(array[0], mm)         // 2 node list
array[0] = null
mm = merge(array[1], mm)         // 4 node list
array[1] = null
array[2] = mm

一旦最后一个节点被合并到数组中，数组中的所有列表将被合并形成一个排序列表：

        mm = empty list
        for(i = 0; i < 32; i++){
            if(all[i] != null){
                mm = merge(all[i], mm);
                all[i] = null;    // (for garbage collection)
            }
        }

Java 的原生双 linked 列表 class 不提供在列表内或列表之间移动节点的方法，因此必须删除节点从列表的前面检索一个元素，当一个元素附加到列表的后面时必须创建一个节点，这是一个额外的开销。在 C++ 标准 double link list class std::list 的情况下，std::list::splice() 可用于在列表内或列表之间移动节点，从而减少开销，例如dst.splice(dst.end(), src, src.begin())，它将开始节点（第一个节点）从src移动到dst的结束节点（最后一个节点）。

    public static LinkedList<Integer> merge(LinkedList<Integer> ll,
                                     LinkedList<Integer> rr)
    {
        if(ll.isEmpty())
            return rr;
        if(rr.isEmpty())
            return ll;
        LinkedList<Integer> mm = new LinkedList<>();
        while(true){
            if(ll.getFirst().compareTo(rr.getFirst()) <= 0){
                mm.add(ll.removeFirst());
                if(!ll.isEmpty())
                    continue;
                mm.addAll(rr);
                break;
            } else {
                mm.add(rr.removeFirst());
                if(!rr.isEmpty())
                    continue;
                mm.addAll(ll);
                break;
            }
        }
        return mm;
    }

    public static LinkedList<Integer> mergeSort(LinkedList<Integer> ll)
    {
        if(ll == null || ll.size() < 2)
            return ll;
        int i;
        final int ASZ = 32;                 // create array (of nulls) 
        LinkedList<Integer>[] all= new LinkedList[ASZ];
        // merge nodes into array
        LinkedList<Integer> mm;
        do{
            mm = new LinkedList<>();        // mm = next node
            mm.add(ll.removeFirst());
                                            // merge mm into array
            for(i = 0; (i < ASZ) && (all[i] != null); i++){
                mm = merge(all[i], mm);
                all[i] = null;
            }
            if(i == ASZ)                    // don't go past end of array
                i--;
            all[i] = mm;
        }while(!ll.isEmpty());
        // merge array into single list
        mm = new LinkedList<>();
        for(i = 0; i < ASZ; i++){
            if(all[i] != null){
                mm = merge(all[i], mm);
                all[i] = null;
            }
        }
        return (mm);
    }

测试代码，排序 400 万 (2^22) 个节点大约需要 3 到 5 秒。

public static void main(String[] args) {
    final int COUNT = 4*1024*1024; 
    LinkedList<Integer> ll = new LinkedList<>();
    Random r = new Random();
    for(int i = 0; i < COUNT; i++)
        ll.addLast(r.nextInt());
    long bgn, end;
    bgn = System.currentTimeMillis();
    ll = mergeSort(ll);
    end = System.currentTimeMillis();
    System.out.println("milliseconds " + (end-bgn));
    // check sort
    int i;
    i = ll.removeFirst();
    int j = i;
    while(!ll.isEmpty()){
        j = ll.removeFirst();
        if(i > j)
            break;
        i = j;
    }
    if(i == j)
        System.out.println("passed");
    else
        System.out.println("failed");
 }

在合并代码中，我使用循环而不是 addAll 获得了更快和更一致的运行次，从 3 到 5 秒减少到 2.8 到 3.2 秒，但分配声明使用 addAll .

                //  mm.addAll(rr);    // replace with loop is faster
                do
                    mm.add(rr.removeFirst());
                while(!rr.isEmpty());

Answer 2

就让你的方法奏效而言，你已经很接近了。这是我想出的。我更改了逻辑以创建新列表以包含每个级别的结果，而不是在拆分列表时创建新列表。没有理由为了保持顺序相同而复制列表。需要新鲜存储的是新订单中的列表。这限制了副本的数量，我认为这使逻辑更容易，因为您可以只附加到每个结果列表的末尾，而不必使用逻辑来设置每个列表中的正确位置。

import java.util.Arrays;
import java.util.LinkedList;

class Test {

    public static LinkedList<Integer> mergeSort(LinkedList<Integer> list, int start, int count) {
    
        if (count < 2) {
            LinkedList<Integer> result = new LinkedList<>();
            result.add(list.get(start));
            return result;
        }

        int size1 = count / 2;
        int size2 = count - size1;

        LinkedList<Integer> list_1 = mergeSort(list, start, size1);
        LinkedList<Integer> list_2 = mergeSort(list, start + size1, size2);

        return merge(list_1, list_2);
    }

    public static LinkedList<Integer> merge(LinkedList<Integer> list_1, LinkedList<Integer> list_2) {

        LinkedList<Integer> result = new LinkedList<>();

        int i = 0, j = 0;
        while (i < list_1.size() && j < list_2.size())
            if (list_1.get(i) < list_2.get(j))
                result.add(list_1.get(i++));
            else
                result.add(list_2.get(j++));
        while (i < list_1.size())
            result.add(list_1.get(i++));
        while (j < list_2.size())
            result.add(list_2.get(j++));

        return result;
    }

    public static LinkedList<Integer> mergeSort(LinkedList<Integer> list) {
        return mergeSort(list, 0, list.size());
    }

    public static void main(String[] args) {
        LinkedList<Integer> myList = new LinkedList<>(Arrays.asList(22, 45, 1234, 77, 4, 1111, 999, 12, 88, 44, 7777, 22, 33, 44, 666));
        LinkedList<Integer> sorted = mergeSort(myList);
        System.out.println(sorted);
    }
}

结果：

[4, 12, 22, 22, 33, 44, 44, 45, 77, 88, 666, 999, 1111, 1234, 7777]

更新：正如@rcgldr 指出的那样，上述解决方案不符合规定的准则。使用这个新版本的 merge() 方法，符合准则。请注意，这并没有使算法更加高效（两个版本都创建了很多列表并且非常低效），但它确实节省了一堆步行到列表中的随机位置以支持从每个列表的前面开始工作：

public static LinkedList<Integer> merge(LinkedList<Integer> list_1, LinkedList<Integer> list_2) {

    LinkedList<Integer> result = new LinkedList<>();

    while (list_1.size() > 0 && list_2.size() > 0)
        if (list_1.peek() < list_2.peek()) {
            result.add(list_1.getFirst());
            list_1.remove();
        }
        else {
            result.add(list_2.getFirst());
            list_2.remove();
        }
    result.addAll(list_1);
    result.addAll(list_2);

    return result;
}

另请注意，调用 getFirst() 然后调用 remove() 是多余的。 remmove() 可以单独调用以获取下一个元素并将其从列表中删除。我调用了这两种方法来满足要求。

Java 排序程序

Java Program to sort

java

mergesort