如何在MergeSort中打印逐步處理

Question

我無法打印出MergeSort。我需要幫助打印出每一步的過程，因爲它正在對ArrayList進行排序。

下面的例子是從插入排序，因爲我有它打印在每一次它交換ArrayList中兩個元素：

11 79 60 45 START

11 45 60 79 FINISH

反正有用於歸併做到這一點，而示出了從第一整個陣列藝術才能完成（如上面？）

代碼：

import java.util.ArrayList; 

public class Merge 
{ 
    public static void main (String [] args) 
    { 
     Merge run = new Merge(); 
     run.test(); 
    } 

    public void test () 
    { 
     ArrayList<Integer> numbers = new ArrayList<Integer>(); 
     for (int i = 0; i < 16; i++) 
     { 
      numbers.add(new Integer(1 + (int)(Math.random() * 100))); 
     } 
     printArray(numbers); 
     mergeSort(numbers); 
     printArray(numbers); 
    } 

    public void printArray (ArrayList<Integer> array) 
    { 
     System.out.println("\n\n"); 
     for (int i = 0; i < array.size(); i++) 
     { 
      System.out.printf("%-5d",array.get(i).intValue()); 
     } 
     System.out.println("\n\n"); 
    } 

    public void mergeSort (ArrayList<Integer> array) 
    { 
     int length = array.size(); 
     if (length < 2) 
     { 
      return; // the array is already sorted in this case 
     } 
     // divide 
     ArrayList<Integer> array1 = new ArrayList<Integer>(); 
     ArrayList<Integer> array2 = new ArrayList<Integer>(); 
     int i = 0; 

     while (i < length/2) 
     { 
      array1.add(array.remove(0)); // move the first n/2 elements to array1 
      i++; 
     } 
     while (!array.isEmpty()) 
     { 
      array2.add(array.remove(0)); // move the rest to array2 
     } 

     mergeSort(array1); 
     mergeSort(array2); 
     merge(array1,array2,array); 
    } 

    public void merge (ArrayList<Integer> array1, ArrayList<Integer> array2, ArrayList<Integer> array) 
    { 
     while (!array1.isEmpty() && !array2.isEmpty()) 
     { 
      if ((array1.get(0).compareTo(array2.get(0)) <= 0)) 
      { 
       array.add(array1.remove(0)); 
      } 
      else 
      { 
       array.add(array2.remove(0)); 
      } 
     } 
     while(!array1.isEmpty()) // move the remaining elements of array1 
     { 
      array.add(array1.remove(0)); 
     } 
     while(!array2.isEmpty()) // move the remaining elements of array2 
     { 
      array.add(array2.remove(0)); 
     } 
    } 
} 

Answer 1

如果你的推移，一些偏移mergeSort，您可以打印子陣列縮進到哪裏會是全陣列當你進行交換時，但由於你只傳遞數組的一部分，你將無法以這種方式顯示完整的數組。但是，有一個更快的方法可以讓你。

不是創建新數組並傳遞它們，而是傳遞數組和2個索引，即開始點和結束點。所以你說mergeSort(array, 0, n)爲第一個，然後mergeSort(array, 0, n/2)和mergeSort(array, n/2, n)爲遞歸調用。你只在這些邊界內進行分裂和合並。然後在合併時，可以打印出整個合併的數組。這將顯示每次合併時的步驟。在底層，它會顯示1-1交換（如果它發生）。這是您可以在合併排序中看到的唯一「一步一步」。

Answer 2

無法看到您的代碼很難確切知道，但我從這裏獲取Mergesort Implementation：http://www.vogella.de/articles/JavaAlgorithmsMergesort/article.html。
我已經更新了它打印出你想要的。

public class Mergesort 
{ 
    private int[] numbers; 
    private int[] helper; 

    private int number; 

    public void sort(int[] values) 
    { 
     this.numbers = values; 
     number = values.length; 
     this.helper = new int[number]; 

     System.out.println("START"); 

     mergesort(0, number - 1); 

     System.out.println("END"); 
    } 

    private void mergesort(int low, int high) 
    { 
     // Check if low is smaller then high, if not then the array is sorted 
     if (low < high) 
     { 
      // Get the index of the element which is in the middle 
      int middle = (low + high)/2; 
      // Sort the left side of the array 
      mergesort(low, middle); 
      // Sort the right side of the array 
      mergesort(middle + 1, high); 
      // Combine them both 
      merge(low, middle, high); 
     } 
    } 

    private void merge(int low, int middle, int high) 
    { 

     // Copy both parts into the helper array 
     for (int i = low; i <= high; i++) 
     { 
      helper[i] = numbers[i]; 
     } 

     int i = low; 
     int j = middle + 1; 
     int k = low; 

     // Copy the smallest values from either the left or the right side back 
     // to the original array 
     while (i <= middle && j <= high) 
     { 
      if (helper[i] <= helper[j]) 
      { 
       numbers[k] = helper[i]; 
       i++; 
      } 
      else 
      { 
       numbers[k] = helper[j]; 
       j++; 
      } 
      k++; 
     } 

     // Copy the rest of the left side of the array into the target array 
     while (i <= middle) 
     { 
      numbers[k] = helper[i]; 
      k++; 
      i++; 
     } 

    } 

    private void printArray() 
    { 
     for(int x : numbers) 
      System.out.print(x + " "); 

     System.out.println(" "); 
    } 
} 

如果你不想打印到你可以建立輸出到輸出的字符串，返回它，當你完成所有的控制檯。

Answer 3

這是一個小的合併排序算法程序。我從 http://en.wikipedia.org/wiki/Merge_sort複製算法。您可以將其作爲JUnittest運行或運行主方法。

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 
import junit.framework.TestCase; 

/** 
* Simple MergeSortTest 
*/ 

public class MergeSortTest extends TestCase { 


private static int FIRST_ENTRY = 0; 

public static void main(String[] args) { 
    MergeSortTest mergesorttest = new MergeSortTest(); 
    Integer [] unsortedInt = {1,38, 27, 110, 9, 82, 10, 100, 299, 13}; 
    List<Integer> unsorted = Arrays.asList(unsortedInt); 
    List<Integer> sorted = mergesorttest.mergeSort(unsorted); 
    System.out.println(sorted.toString()); 
} 

public void testMergeSort() { 
    Integer [] unsortedInt = {1,38, 27, 110, 9, 82, 10, 100, 299, 13}; 
    List<Integer> unsorted = Arrays.asList(unsortedInt); 
    List<Integer> sorted = mergeSort(unsorted); 
    assertEquals("[1, 9, 10, 13, 27, 38, 82, 100, 110, 299]", sorted.toString()); 
} 

private List<Integer> mergeSort(List<Integer> list) { 
    List<Integer> result; 
    List<Integer> left = new ArrayList<Integer>(); 
    List<Integer> right = new ArrayList<Integer>();; 
    int middle; 
    int counter; 
    if (list.size() <= 1) { 
     return list; 
    } 
    middle = list.size()/2; 

    for (counter = 0; counter < middle; counter++) { 
     left.add(list.get(counter)); 
    } 

    for (counter = middle; counter < list.size(); counter++) { 
     right.add(list.get(counter)); 
    } 

    left = mergeSort(left); 
    right = mergeSort(right); 
    result = merge(left, right); 
    System.out.println(result); 
    return result; 
} 

private List<Integer> merge(List<Integer> left, List<Integer> right) { 
    List<Integer> result = new ArrayList<Integer>(); 
    while (!left.isEmpty() || !right.isEmpty()) { 
     if (!left.isEmpty() && !right.isEmpty()) { 
      if (left.get(FIRST_ENTRY) <= right.get(FIRST_ENTRY)) { 
       handle(left, result); 
      } else { 
       handle(right, result); 
      } 
     } else if (!left.isEmpty()) { 
      handle(left, result); 
     } else if (!right.isEmpty()) { 
      handle(right, result); 
     } 
    } 
    return result; 
} 

private void handle(List<Integer> list, List<Integer> result) { 
    if (!list.isEmpty()) { 
     result.add(list.get(FIRST_ENTRY)); 
     list.remove(FIRST_ENTRY); 
    } 
} 

}