java中的排序合併代碼需要一些說明

Question

請你能在下面解釋一些行（我把？放在需要解釋的每行前面）。提前致謝 ！ 我知道：對輸入序列S 合併排序與n個元素由三個步驟組成： 鴻溝：劃分S成兩個序列S1和大約n/2個元件S2各 重複執行：遞歸地排序S1和S2 治：將S1和S2合併成一個獨特的排序序列

但是當我讀代碼時，我迷失了方向，你能不能指導我。

public class MergeSort { 
     public static int[] mergeSort(int [] list) { 
      if (list.length <= 1) { 
       return list; 
      } 

      // Split the array in half 
      int[] first = new int[list.length/2]; // ok 
      int[] second = new int[list.length - first.length]; // ? 
      System.arraycopy(list, 0, first, 0, first.length); // ? 
      System.arraycopy(list, first.length, second, 0, second.length); // not sure ? 

      // Sort each half 
      mergeSort(first); // ok 
      mergeSort(second); // ok 

      // Merge the halves together, overwriting the original array 
      merge(first, second, list); // ok 
      return list; // ok 
     } 

     private static void merge(int[] first, int[] second, int [] result) { // explain in general ? 
      // Merge both halves into the result array 
      // Next element to consider in the first array 
      int iFirst = 0; 
      // Next element to consider in the second array 
      int iSecond = 0; 

      // Next open position in the result 
      int j = 0; 
      // As long as neither iFirst nor iSecond is past the end, move the 
      // smaller element into the result. 
      while (iFirst < first.length && iSecond < second.length) { // ??!! 
       if (first[iFirst] < second[iSecond]) { 
        result[j] = first[iFirst]; 
        iFirst++; 
        } else { 
        result[j] = second[iSecond]; 
        iSecond++; 
       } 
       j++; 
      } 
      // copy what's left 
      System.arraycopy(first, iFirst, result, j, first.length - iFirst); 
      System.arraycopy(second, iSecond, result, j, second.length - iSecond); 
     } 

     public static void main(String args[]) throws Exception 
     { 
      String list=""; 
      int i=0,n=0; 

      MergeSort s= new MergeSort(); 
      ArrayList<Integer> arrlist=new ArrayList<Integer>(); 
      System.out.println(" "); 
      System.out.println(" "); 
      System.out.println("Please enter the list of elements,one element per line"); 
      System.out.println(" write 'STOP' when list is completed "); 
      BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); 
      while(!(list=bf.readLine()).equalsIgnoreCase("stop")){ 
       int intelement=Integer.parseInt(list); 
       arrlist.add(intelement); 

      } 

      int elementlist[] = new int[arrlist.size()]; 
      Iterator<Integer> iter = arrlist.iterator(); 
      for (int j=0;iter.hasNext();j++) { 
       elementlist[j] = iter.next(); 
      } 

      elementlist=mergeSort(elementlist); // ? 
      System.out.println(" "); 
      System.out.println(" "); 
      System.out.println(" "); 
      System.out.println("Values after Merge Sort : "); 
      for (int j=0;j<elementlist.length;j++) { 
       System.out.println(elementlist[j]+" "); 
      } 
     } 
    } 

Answer 1

在int[] first = new int[list.length/2];和int[] second = new int[list.length - first.length];方法將所述列表分成2個陣列，可以說你的列表具有長度爲5第一將對第二2作爲其大小和3。在

System.arraycopy(list, 0, first, 0, first.length); 
System.arraycopy(list, first.length, second, 0, second.length); 

您的填充從清單陣列二者的第一和第二陣列（複製list[0],list[1]到第一陣列和list[2],list[3],list[4]到第二陣列）。

在private static void merge(int[] first, int[] second, int [] result)要合併first和second陣列和重寫result陣列 在while環你把第一和第二陣列的第一元件和比較它們並移動最小到result[0]然後遞增指針通過相應陣列使用if and else聲明，並且現在您將first和second陣列中的最小元素放置在result[0]中。

您增加j，這意味着在此迭代中，您將把第二小元素放在result[1]等等中。

在elementlist=mergeSort(elementlist);您在排序elementlist通過調用您的mergeSort(int [] list);方法。