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);方法。