Java中的简单合并排序

脑皮质

我正在尝试在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");
    }
}

奥斯丁·里斯

我知道这真的很晚，但是我有您要的正确答案！

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循环遍历列表可以帮助您返回正确的值！

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。