遞歸合併排序

Question

我正在嘗試爲類編寫一個遞歸合併排序方法。當我嘗試mergeSort(leftArr)和mergeSort(rightArr)時，我總是收到stackoverflow。爲什麼我的基本情況沒有工作？

import java.util.Arrays; 

public class SortingAlgorithms { 
    public static void mergeSort(int[] list){ 

     int mid = list.length/2; 
     int [] leftArr = new int [mid]; 
     int [] rightArr; 


     if (mid % 2 == 0) { 
      rightArr = new int [mid]; 
     } 
     else{ 
      rightArr = new int [mid + 1]; 
     } 

     if (leftArr.length < 2 && rightArr.length < 2){ 
      list = mergeHelper(leftArr, rightArr); 
     } 

     // copying first half of array 
     for (int i = 0; i < mid; i++){ 
      leftArr[i] = list[i]; 
     } 

     // copying second half of array 
     int placeHolder = 0; 
     for (int i = mid; i < list.length; i++){ 
      if (placeHolder < rightArr.length) { 
       rightArr[placeHolder] = list[i]; 
       placeHolder++; 
      } 
     } 

     mergeSort(leftArr); 
     mergeSort(rightArr); 
    } 

    public static int[] mergeHelper(int[] leftArr, int[] rightArr){ 

     int leftIndex = 0; 
     int rightIndex = 0; 
     int sortedArrayIndex = 0; 
     int[] newList = new int[leftArr.length + rightArr.length]; 

     while (leftIndex < leftArr.length || rightIndex < rightArr.length){ 
      if (leftIndex < leftArr.length && rightIndex < rightArr.length){ 
       if(leftArr[leftIndex] > rightArr[rightIndex]){ 
        newList[sortedArrayIndex] = rightArr[rightIndex]; 
        rightIndex++; 
        sortedArrayIndex++; 
       } 
       else { 
        newList[sortedArrayIndex] = leftArr[leftIndex]; 
        leftIndex++; 
        sortedArrayIndex++; 
       } 
      } 

      else if (leftIndex < leftArr.length && rightIndex == rightArr.length){ 
       newList[sortedArrayIndex] = leftArr[leftIndex]; 
       leftIndex++; 
       sortedArrayIndex++; 
      } 

      else if (rightIndex < rightArr.length && leftIndex == leftArr.length){ 
       newList[sortedArrayIndex] = rightArr[rightIndex]; 
       rightIndex++; 
       sortedArrayIndex++; 
      } 
     } 
     return newList; 
    } 

    public static void populateArray(int[] list){ 
     for (int i = 0; i < list.length; i++){ 
      list[i] = (int) ((Math.random() * 100)); 
     } 
    } 

    public static void main(String[] args){ 

     int [] list = new int [10]; 
     populateArray(list); 
     System.out.println(Arrays.toString(list)); 
     mergeSort(list); 
     System.out.println(Arrays.toString(list)); 


     //proof that mergeHelper() works 
     //  int[] left = {1,3,5,7,9}; 
     //  System.out.println(Arrays.toString(left)); 
     //  int[] right = {0,2,4,6,8}; 
     //  System.out.println(Arrays.toString(right)); 
     //  System.out.println(Arrays.toString(mergeHelper(left,right))); 

} 
} 

Answer 1

您的權利ARArr長度確定不好。更正：

rightArr = new int [list.length - mid];

Answer 2

## This is a way to use merge sort in c#, with recursion. ## 



static void Main(string[] args) 
    { 
     List<int> list = new List<int>(); 
     int m = int.Parse(Console.ReadLine()); 
     for (int i = 0; i < m; i++) 
     { 
      int p = int.Parse(Console.ReadLine()); 
      list.Add(p); 
     } 
     Console.WriteLine(String.Join(",", MergeSort(list))); 
    } 
    static List<int> MergeSort(List<int> array) 
    { 
     List<int> output = new List<int>(); 
     if (array.Count == 1) 
     { 
      return array; 
     } 
     if (array.Count == 2) 
     { 
      if (array[0] > array[1]) 
      { 
       int a = array[1]; 
       array[1] = array[0]; 
       array[0] = a; 
       return array; 
      } 
      else 
      { 
       return array; 
      } 
     } 
     else 
     { 
      List<int> firstList = new List<int>(); 
      List<int> secondList = new List<int>(); 
      for (int i = 0; i < array.Count/2; i++) 
      { 
       firstList.Add(array[i]); 
       secondList.Add(array[i + array.Count/2]); 
      } 
      if (array.Count % 2 != 0) 
      { 
       secondList.Add(array[array.Count - 1]); 
      } 
      firstList = MergeSort(firstList); 
      secondList = MergeSort(secondList); 
      int k = 0; 
      int j = 0; 
      int size = firstList.Count + secondList.Count; 
      int markerFirst = firstList.Count; 
      int markerSecond = secondList.Count; 

      for (int i = 0; i < size; i++) 
      { 
       if (k == markerFirst) 
       { 
        output.Add(secondList[j]); 
        j++; 
        continue; 
       } 
       if (j == markerSecond) 
       { 
        output.Add(firstList[k]); 
        k++; 
        continue; 
       } 
       if (firstList[k] < secondList[j]) 
       { 
        output.Add(firstList[k]); 
        k++; 
       } 
       else 
       { 
        output.Add(secondList[j]); 
        j++; 
       } 
      } 
     } 
     return output; 
    } 
} 

} 

Answer 3

代碼有一些問題：

1）沒有一個條件來停止這樣的代碼遞歸低於「歸併」 method.You收到stackoverflows因爲你的代碼處於無限循環。在「mergeSort」方法的第一行添加此代碼。

if(list.length <= 1) 
    return; 

2）修正「rightArr」的大小......這2個更正你的代碼運行，但不排序。

int[] rightArr = new int [list.length - mid]; 

//  if (mid % 2 == 0) { 
//   rightArr = new int[mid]; 
//  } else { 
//   rightArr = new int[mid + 1]; 
//  } 

打開在一個更簡單的方法的代碼...

import java.util.Arrays; 

public class MergeSort { 

    public static void main(String[] args) { 
     Integer[] itens = {2,6,4,9,1,3,8,7,0}; 

     Integer[] tmp = new Integer[itens.length]; 
     int left = 0; 
     int right = itens.length - 1; 

     mergeSort(itens, tmp, left, right); 

     System.out.println(Arrays.toString(itens)); 
    } 

    private static void mergeSort(Integer[] itens, Integer[] tmpArray, int left, int right) { 

     if(itens == null || itens.length == 0 || left >= right){ 
      return; 
     } 

     int midle = (left + right)/2; 

     mergeSort(itens, tmpArray, left, midle); 
     mergeSort(itens, tmpArray, midle + 1, right); 

     merge(itens, tmpArray, left, midle + 1, right); 
    } 

    private static void merge(Integer[] itens, Integer[] tmpArray, int left, int right, int rightEnd) { 
     int leftEnd = right - 1; 
     int tmpIndex = left; 

     while (left <= leftEnd && right <= rightEnd){ 
      if (itens[left] < itens[right]){ 
       tmpArray[tmpIndex++] = itens[left++]; 
      } else { 
       tmpArray[tmpIndex++] = itens[right++]; 
      } 
     } 

     while (left <= leftEnd) { // Copy rest of LEFT half 
      tmpArray[tmpIndex++] = itens[left++]; 
     } 
     while (right <= rightEnd) { // Copy rest of RIGHT half 
      tmpArray[tmpIndex++] = itens[right++]; 
     } 
     while(rightEnd >= 0){ // Copy TEMP back 
      itens[rightEnd] = tmpArray[rightEnd--]; 
     } 
    } 
}