在Java 7中实现合并排序 [英] Implementing merge sort in java 7

问题描述

我在用Java实现合并排序时遇到问题.不幸的是，我几乎一周都在寻找错误，但没有结果.入口处的ArrayList与输出相同.

I have a problem with implementation of merge sort in java. I am looking for the error almost week unfortunately without result. ArrayList at the entrance is the same as the output.

import java.util.ArrayList;
import java.util.Scanner;

public class MergeSort 
{
    private ArrayList<Integer> basicArrayList = new ArrayList<Integer>();
    ArrayList<Integer> arrayListA = new ArrayList<Integer>();
    ArrayList<Integer> arrayListB = new ArrayList<Integer>();
    Scanner input = new Scanner(System.in);
    private int firstIndexOfArrayList = 0;
    private int lastIndexOfArrayListA;
    private int lastIndexOfArrayListB;

    public void Scal(ArrayList<Integer> basicArrayList, int p, int q, int r) {
        this.firstIndexOfArrayList = p;
        this.lastIndexOfArrayListA = q;
        this.lastIndexOfArrayListB = r;

        int numberOfElementsArrayListA = lastIndexOfArrayListA
                - firstIndexOfArrayList + 1;
        int numberOfElementsArrayListB = lastIndexOfArrayListB
                - lastIndexOfArrayListA;

        for (int i = 0; i < numberOfElementsArrayListA; i++) {
            arrayListA.set(i, basicArrayList.get(firstIndexOfArrayList + i));
        }

        for (int j = 0; j < numberOfElementsArrayListB; j++) {
            arrayListB.set(j, basicArrayList.get(lastIndexOfArrayListA + j));
        }

        arrayListA.add(Integer.MAX_VALUE);
        arrayListB.add(Integer.MAX_VALUE);
        int i = 0;
        int j = 0;

        for (int k = firstIndexOfArrayList; k <= lastIndexOfArrayListB; k++) {
            if (arrayListA.get(i) <= arrayListB.get(j)) {
                basicArrayList.set(k, arrayListA.get(i));
                i = i + 1;
            } else {
                basicArrayList.set(k, arrayListB.get(j));
                j = j + 1;
            }
        }
    }

    public void MergeSort(ArrayList basicArrayList, int p, int r) {
        this.firstIndexOfArrayList = p;
        this.lastIndexOfArrayListB = r;

        if (firstIndexOfArrayList < lastIndexOfArrayListB) {
            int lastIndexOfArrayListA = (firstIndexOfArrayList + lastIndexOfArrayListB) / 2;
            MergeSort(basicArrayList, firstIndexOfArrayList,
                    lastIndexOfArrayListA);
            MergeSort(basicArrayList, lastIndexOfArrayListA + 1,
                    lastIndexOfArrayListB);
            Scal(basicArrayList, firstIndexOfArrayList,
                    lastIndexOfArrayListA,
                    lastIndexOfArrayListB);
        }
    }

    public void setSize() {
        System.out.println("Enter the number of elements to sort: ");
        this.lastIndexOfArrayListB = input.nextInt();
    }

    public int getSize() {
        return lastIndexOfArrayListB;
    }

    public void setData() {
        System.out.println("Enter the numbers: ");
        for (int i = 0; i < lastIndexOfArrayListB; i++) {
            int number;
            number = input.nextInt();
            basicArrayList.add(number);
        }
    }

    public void getTable() {
        System.out.println(basicArrayList.toString());
    }

    public static void main(String[] args) {
        MergeSort output = new MergeSort();
        output.setSize();

        output.setData();

        output.MergeSort(output.basicArrayList,
                output.firstIndexOfArrayList, (output.getSize() - 1));

        output.getTable();
    }

}

推荐答案

在修复代码方面，我对此有所了解，据我所知这似乎可行.为此，您必须更改很多代码，但现在确实可以正确地对所有Integers进行排序

In terms of fixing your code I had a crack at it and as far as I can tell this seems to work. To do this a lot of your code had to be changed but it does now sort all Integers properly

import java.util.ArrayList;
import java.util.Scanner;

public class MergeSort 
{
    private ArrayList<Integer> basicArrayList = new ArrayList<Integer>();
    Scanner input = new Scanner(System.in);
    private int numbersToSort;

    public void doMergeSort(int firstIndexOfArrayList,int lastIndexOfArrayListB, ArrayList<Integer> arrayList)
    {
        if(firstIndexOfArrayList<lastIndexOfArrayListB && (lastIndexOfArrayListB-firstIndexOfArrayList)>=1)
        {
            int mid = (lastIndexOfArrayListB + firstIndexOfArrayList)/2;
            doMergeSort(firstIndexOfArrayList, mid, arrayList);
            doMergeSort(mid+1, lastIndexOfArrayListB, arrayList);
            Scal(firstIndexOfArrayList,mid,lastIndexOfArrayListB, arrayList);            
        }       
    }   

    public void Scal(int firstIndexOfArrayList,int lastIndexOfArrayListA,int lastIndexOfArrayListB, ArrayList<Integer> arrayList)
    {
        ArrayList<Integer> mergedSortedArray = new ArrayList<Integer>();

        int leftIndex = firstIndexOfArrayList;
        int rightIndex = lastIndexOfArrayListA+1;

        while(leftIndex<=lastIndexOfArrayListA && rightIndex<=lastIndexOfArrayListB)
        {
            if(arrayList.get(leftIndex)<=arrayList.get(rightIndex))
            {
                mergedSortedArray.add(arrayList.get(leftIndex));
                leftIndex++;
            }
            else
            {
                mergedSortedArray.add(arrayList.get(rightIndex));
                rightIndex++;
            }
        }

        while(leftIndex<=lastIndexOfArrayListA)
        {
            mergedSortedArray.add(arrayList.get(leftIndex));
            leftIndex++;
        }

        while(rightIndex<=lastIndexOfArrayListB)
        {
            mergedSortedArray.add(arrayList.get(rightIndex));
            rightIndex++;
        }

        int i = 0;
        int j = firstIndexOfArrayList;

        while(i<mergedSortedArray.size())
        {
            arrayList.set(j, mergedSortedArray.get(i++));
            j++;
        }
    }

    public void setSize() 
    {
        System.out.println("Enter the number of elements to sort: ");
        this.numbersToSort = input.nextInt();
    }

    public int getSize() 
    {
        return numbersToSort;
    }

    public void setData() 
    {
        System.out.println("Enter the numbers: ");
        for (int i = 0; i < numbersToSort; i++) 
        {
            int number;
            number = input.nextInt();
            basicArrayList.add(number);
        }
    }

    public void getTable() 
    {
        System.out.println(basicArrayList.toString());
    }

    public void runSort(ArrayList<Integer> arrayList)
    {
        doMergeSort(0, this.numbersToSort-1, arrayList);
    }

    public static void main(String[] args) 
    {
        MergeSort output = new MergeSort();
        output.setSize();
        output.setData();
        output.runSort(output.basicArrayList);
        output.getTable();
    }
}

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