Javaのソート・マージ・コードにはいくつかの説明が必要です

Question

以下の行をいくつか説明してください（説明が必要な各行の先頭に？を付けてください）。前もって感謝します ！ 入力シーケンスSのn要素のマージソートは、次の3つのステップで構成されています。 分割：パーティションSを約n/2要素の2つのシーケンスS1と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つの配列にリストを分割され、リストは、第二のためにその大きさとして2と3を持って第5の長さを有していると言うことができます。

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

であなたは、（第二の配列に最初の配列とlist[2],list[3],list[4]にlist[0],list[1]コピー）リストアレイから第一及び第二の両方の配列を移入。

次いでによって相応配列へのポインタをインクリメントprivate static void merge(int[] first, int[] second, int [] result)では、firstとsecond配列をマージしていて、第一および第二の配列の最初の要素を取るwhileループにresultアレイ を上書きし、それらを比較しresult[0]に最小の移動しますif and elseステートメントを使用して、result[0]に配置されたfirstとsecondの配列の中で最小の要素を持つようになりました。

あなたがインクリメントしたのはjです。つまり、この繰り返しでは、2番目に小さい要素をresult[1]などに置きます。

elementlist=mergeSort(elementlist);では、elementlistをmergeSort(int [] list);メソッドを呼び出してソートしています。