Java中的合并排序问题 [英] problems with merge sort in java

问题描述

我是stackoverflow的新手，我在编写程序以合并可比较数组列表时需要一些帮助.我已经在这个代码上工作了几个小时无济于事.该程序需要正确运行，因为我正在为一门计算机科学课做这件事，并且下一个作业要求我们测试不同种类的效率.这是代码:

i'm brand new to stackoverflow and i need some help with writing a program to mergesort an arraylist of comparables. i have worked on this code for hours to no avail. the program needs to work correctly, because i am doing it for a computer science class, and the very next assignment requires us to test the efficiency of different sorts. here's the code:

合并方法:

public static void merge(ArrayList <Comparable> a, int first, int mid, int last){
    ArrayList <Comparable> b = new ArrayList();
    for(int k = first; k <= last; k++){
        b.add(a.get(k));
    }

    System.out.println("b now contains " + b);
    int middle =b.size() /2;
    for(int i = first; i <= last; i++){
        //System.out.println("mid: " + b.size() /2);
        //System.out.println("b: " + b);
        //System.out.println("a: " + a);
        //System.out.println("i: " + i);
        if(middle == b.size()){
            a.set(i, b.remove(0));
            middle--;
        }else if(middle == 0){
            a.set(0, b.remove(0));
        }else if(b.get(0).compareTo(b.get(middle)) < 0){
            System.out.println("moving " + b.get(0) + " from b[0] to a[" + 
                i + "] because " + b.get(0) + " is less than " + b.get(middle));
            a.set(i, b.remove(0));
            middle--;
            System.out.println("b now contains " + b);
        }else{
            System.out.println("moving " + b.get(middle) + " from b[" + 
                b.size() /2 + "] to a[" + i + "] because " + b.get(0) + 
                    " is greater than " + b.get(middle));
            a.set(i, b.remove(middle));
            //middle--;
            System.out.println("b now contains " + b);
        }
    }

    System.out.println();
    System.out.println("Merge");
    System.out.println(a);
    System.out.println();
}

合并排序方法:

public static void mergeSort(ArrayList <Comparable> a, int first, int last){
    if(first < last){
        int mid = first + (last - first) /2;
        System.out.println("mergeSorting " + a.subList(first, last + 1));
        mergeSort(a, first, mid);
        System.out.println("mergeSorting " + a.subList(first, mid + 1));
        mergeSort(a, mid + 1, last);
        System.out.println("merging " + a.subList(first, mid + 1) + 
            " and " + a.subList(mid + 1, last + 1));
        merge(a, first, mid, last);
    }
    System.out.println();
    System.out.println("base case");
    System.out.println();
}

我认为merge方法存在问题，但我不确定.

I think that there is a problem with the merge method, but i'm not sure.

我的代码似乎对列表进行了不正确的排序，即:

my code seems to be sorting the list incorrectly, i.e:

Input:
[7,1,9,9,5,4,8,9,10,4] 

Output:
[4,8,9,4,10,10,5,9,9,7]

推荐答案

mergeSort算法是可以的.我只是定义了ArrayList的类型以避免警告

The mergeSort algorithm is ok. I just defined the type of ArrayList to avoid the warning

   public static void mergeSort(ArrayList <Comparable> a, int first, int last){
        if(first < last){
            int mid = first + (last - first) /2;
        //    System.out.println("mergeSorting " + a.subList(first, mid ));
            System.out.println("First"+first);
            System.out.println("Mid"+mid);
            System.out.println("Last"+last);
            System.out.println("MergeSortCall");
            System.out.println("firstVector " + a.subList(first, mid+1));
            System.out.println("secondVector " + a.subList(mid + 1,last+1));                
            mergeSort(a, first, mid);
            mergeSort(a, mid + 1, last);
            merge(a, first, mid, last);
            System.out.println("mergeVector " + a.subList(first,last+1));
        }

    }

第二部分真的很难确切地知道哪里出了问题，因此我基本上使用您的符号将其替换为更简单的内容.请注意，第二部分只是一个合并"算法.它应该很简单.无论如何，您可以使用它与您的结果进行比较(很抱歉，很难理解第二部分的逻辑，这是您的作业，不是吗?).我正在使用两个向量来提高可读性，但是只有一个是必要的.

The second part is really difficult to know exactly what is wrong so I replaced it for something much simpler using basically your notation. Note that the second part is just a "merge" algorithm. It is supposed to be really simple. Anyway, using this you can compare with your results (sorry it is difficult to understanding the logic of the second part and this is your homework, isn't it?). I'm using two vectors to improve the readability, but only one as you did is necessary.

public static void merge(ArrayList <Comparable> a, int first, int mid, int last){
            ArrayList <Comparable> vectorFirst = new ArrayList<Comparable>();
            ArrayList <Comparable> vectorSecond = new ArrayList<Comparable>();

            for(int k=first;k<=mid;k++){
                vectorFirst.add(a.get(k));
            }
            for(int k=mid+1;k<=last;k++){
                vectorSecond.add(a.get(k));
            }

            int i=first;
            int j=mid+1;
            int k=first-1;
            while((i<=mid)&(j<=last)){
                if(vectorFirst.get(i-first).compareTo(vectorSecond.get(j-mid-1))==-1){
                    k=k+1;
                    a.set(k,vectorFirst.get(i-first));
                    i=i+1;
                }
                else{
                     k=k+1;
                     a.set(k,vectorSecond.get(j-mid-1));
                     j=j+1;
                }
            }
            if(i==mid+1){
                while(j<=last){
                    k=k+1;
                    a.set(k,vectorSecond.get(j-mid-1));
                    j=j+1;
                }
            }
            else{
                while(i<=mid){
                    k=k+1;
                    a.set(k,vectorFirst.get(i-first));
                    i=i+1;
                }
            }


        }

这篇关于Java中的合并排序问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！