Java中的简单合并排序

Question

我正试图在Java中创建一个简单的合并排序程序。我觉得它应该工作，但当我去运行它时，我得到了一个堆栈溢出错误：

Stack overflow at MergeSort.mergeSort(MergeSort.java:24)

我看到这里的其他几个人也有类似的代码问题，但我正在努力解决我的问题。如有任何帮助，我们将不胜感激。

主要代码：

import static java.lang.System.*;
import java.util.Arrays;        
public class MergeSort {
    private static int passCount;
    public static void mergeSort(Comparable[] list)
    {
        passCount = 0;
        mergeSort(list, 0, list.length);
    }
    private static void mergeSort(Comparable[] list, int front, int back)  //O( Log N )
    {
        int mid = (front + back) / 2;
        if (mid == front)
            return;
        mergeSort(list, front, mid);
        mergeSort(list, front, back);
        merge(list, front, back);
    }
    private static void merge(Comparable[] list, int front, int back)  //O(N)
    {
        Comparable[] temp = new Comparable[back - front];
        int i = front;
        int j = (front + back) / 2;
        int k = 0;
        int mid = j;
        while (i < mid && j < back)
        {
            if (list[i].compareTo(list[j]) < 0)
            {
                temp[k] = list[i];
                k++; i++;
            }
            else
            {
                temp[k] = list[j];
                k++; i++;
            }
            while(i < mid)
            {
                temp[k++] = list[i++];
            }
            while (j < back)
            {
                temp[k++] = list[j++];
            }
            for (i = 0; i < back - front; ++i)
            {
                list[front + i] = temp[i];
            }
            out.println("pass " + passCount++ + " " + Arrays.toString(list) + "n");
        }
    }
}

我的跑步者：

public class MergeSortRunner
{
    public static void main(String args[])
    {
        MergeSort.mergeSort(new Comparable[]{ 9, 5, 3, 2 });
        System.out.println("n");
        MergeSort.mergeSort(new Comparable[]{ 19, 52, 3, 2, 7, 21 });
        System.out.println("n");
        MergeSort.mergeSort(new Comparable[]{ 68, 66, 11, 2, 42, 31});
        System.out.println("n");
    }
}

Answer 1

您需要更改：

mergeSort(list, front, back);

收件人：

mergeSort(list, mid, back);

这将导致对mergeSort的无限调用，因为在调用之间不更改任何输入参数。

您可能还想更改：

if(mid==front) return;

至：

if(back - front <= 1) return;

此外，您对该算法的实现选择可能会导致不稳定的排序，因为您正在修改列表。一个更好的选择是让mergeSort返回一个你正在排序的列表，然后实现merge以两个列表作为参数，然后生成一个合并的列表。

Answer 2

我知道这真的很晚了，但我有你想要的正确答案！

import static java.lang.System.*;
import java.util.Arrays;        
public class MergeSort{
private static int passCount;
public static void mergeSort(int[] list)
{
    passCount=0;
    mergeSort(list, 0, list.length);
}
private static void mergeSort(int[] list, int front, int back)  //O( Log N )
{
    int mid = (front+back)/2;
    if(mid==front) return;
    mergeSort(list, front, mid);
    mergeSort(list, mid, back);
    merge(list, front, back);
}
private static void merge(int[] list, int front, int back)  //O(N)
{
   int dif = back-front;
   int[] temp = new int[dif];
   int beg = front, mid = (front+back)/2;
   int saveMid = mid;
   int spot = 0;
   while(beg < saveMid && mid < back) {
      if(list[beg] < list[mid]) {
         temp[spot++] = list[beg++];
      } else {
         temp[spot++] = list[mid++];
      }
   }
   while(beg < saveMid)
      temp[spot++] = list[beg++];
   while(mid < back)
      temp[spot++] = list[mid++];
   for(int i = 0; i < back-front; i++) {
      list[front+i] = temp[i];
   }
    System.out.println("pass " + passCount++ + " " + Arrays.toString(list) + "n");
  }
 }

这是跑步者：

    public class MergeSortRunner {
    public static void main(String[] args) {
    MergeSort.mergeSort(new int[]{9,5,3,2});
    System.out.println();
    MergeSort.mergeSort(new int[]{19,52,3,2,7,21});
    System.out.println();
    MergeSort.mergeSort(new int[]{68,66,11,2,42,31});
    System.out.println();
   }
}

事实证明，使用while循环在列表中循环可以帮助您返回正确的值！

Answer 3

尝试更改

if(mid==front) return;

至

if(back-front<=1) return;