java二路归并排序示例分享

importjava.util.Scanner;
publicclassMergeSort{
   int[]a=null;
   int[]b=null;
   intn;
   Scannersin=null;

   MergeSort()
   {
       a=newint[10000];
       b=newint[10000];
       sin=newScanner(System.in);
   }

   voidsort(intstart,intend)   //排序a[start...end]
   {
       intmid;
　　　　if(start>=end)   //只有一个元素的时候，直接返回
           return;
       else
       {
           mid=(end-start)/2;   //将元素分成两半，分别排序
           sort(start,start+mid);
           sort(start+mid+1,end);

           //归并两个有序的数组a[start...start+mid]和a[start+mid+1...end]
           merge(start,start+mid,end);   
       }
   }

   voidmerge(intstart,intmid,intend)   //归并
   {
       intt=start;
       inti=start,j=mid+1;
       while(i<=mid&&j<=end)
       {
           if(a[i]<a[j])
               b[t++]=a[i++];
           else
               b[t++]=a[j++];
       }
       while(i<=mid)
           b[t++]=a[i++];
       while(j<=end)
           b[t++]=a[j++];

       for(i=start;i<=end;i++)   //排序后的内容写回a数组的相应位置去
           a[i]=b[i];
   }

   voidrun()
   {
       System.out.print("输入要排序的数的个数：");
       n=sin.nextInt();
       for(inti=0;i<n;i++)
           a[i]=sin.nextInt();
       sort(0,n-1);
       System.out.println("排序结果是：");
       //输入要排序的数据
       for(inti=0;i<n;i++)
           System.out.println(a[i]+" ");
   }

   publicstaticvoidmain(String[]args){
       newMergeSort().run();
   }
}