java 中的递归合并排序

Question

我一直在研究归并排序算法和可视化。当我完成编码部分时，这对我来说有点挑战。但是，我仍然进行了带有运行时错误的编码。错误是 NullPointerException。请帮我。这是一个学校项目。

public class test
{       
    public static void main (String[]args)
    {               
        int arr[]={11,34,65,89,1,456,90,85,12,70};
        mergesort(arr,0,9);
        for(int a=0;a<arr.length;a++)
            System.out.println(arr[a]);
    }

    public static void mergesort (int arr[], int low, int high)
    {           
        int middle;
        if(low<high)
        {
        middle = (low+high)/2;
        mergesort(arr,low,middle);
        mergesort(arr,middle+1,high);
        merge(arr,low,middle,high);
        }           
    }

    public static void merge(int arr[], int low, int middle, int high)
    {
        Queue<Integer> buffer1 = new LinkedList<Integer>();     
        Queue<Integer> buffer2 = new LinkedList<Integer>(); 
        int i;

        for(int a=low;a<middle;a++) buffer1.add(arr[a]);
        for(int a=middle+1;a<high;a++) buffer2.add(arr[a]);
        i=low;
        while(!(buffer1.isEmpty()) && !(buffer2.isEmpty()))
        {
            if(buffer1.peek() <= buffer2.peek())
            {
                arr[i] = buffer1.poll();

            } else
            {
                arr[i] = buffer2.poll();                    
            }               
        }
        while(!(buffer1.isEmpty()))
        {
            arr[i] = buffer1.poll();
        }
        while(!(buffer2.isEmpty()))
        {
            arr[i] = buffer2.poll();
        }
    }

}

Answer 1

像这样更改您的 for 循环

for(i=low;i<=middle;i++)
{
    buffer1.add(arr[i]);                
}
for(i=middle+1;i<=high;i++)
{
    buffer2.add(arr[i]);
}

这里low和high分别表示first和的索引数组的最后 个元素。

Answer 2

这是更新后的代码，运行宁可正常，没有编译和运行-time 错误：

public class Merge 
{

public static void mergesort(int arr[], int low, int high)
{
    int middle;
    if(low<high)
    {
        middle = (low+high)/2;
        mergesort(arr,low,middle);
        mergesort(arr,middle+1,high);
        merge(arr,low,middle,high);
    }
}
public static void merge(int arr[], int low, int middle, int high)
{
    Queue<Integer>half1 = new LinkedList<Integer>();
    Queue<Integer>half2 = new LinkedList<Integer>();

    for(int j = low; j<=middle;j++)
        {               
            half1.add(arr[j]);
        }
    for(int j= middle+1 ; j<=high ; j++)
        {
            half2.add(arr[j]);
        }
    int i = low;
    while(!(half1.isEmpty() || half2.isEmpty()))
    {
        if(half1.peek() <= half2.peek())
        {
            arr[i++] = half1.poll();

        }
        else {arr[i++] = half2.poll();}
    }

    while(!half1.isEmpty())
    {
        arr[i++] = half1.poll();
    }
    while(!half2.isEmpty())
    {
        arr[i++] = half2.poll();
    }
}

    public static void main (String[]args)
    {
         int arr[] = {11,45,90,121,67,19,54,28,7,50}; 
         mergesort(arr,0,arr.length-1);

         for(int a=0;a<arr.length;a++)
              System.out.println(arr[a]);
    }
 }

java 中的递归合并排序

Recursive Merge sort in java

java

queue

recursion

merge

mergesort