package org.xiu68.ch02.ex2;

 public class Ex2_14 {

     //基于分治法的归并排序算法

     public static void main(String[] args) {

         int[] a=new int[]{5,5,4,4,3,3,3,2,2,1,1};

         //先归并排序数组，时间复杂度为O(nlog2n)

         mergeSort(a, a.length-1);

         int min=a[0]-1;

         //去掉有序数组中的重复元素，时间复杂度为O(n)

         removeSame(a);

         //总的时间复杂度为O(nlog2n)

         for(int i=0;i<a.length;i++){

             if(a[i]!=min)

                 System.out.print(a[i]+"  ");

         }

     }

     //一次归并，二并一

     public static void merge(int[] start,int[] result,int s,int m,int t){

         //s,m+1为两个有序序列的第一个记录,t为第二个序列的最后一个记录

         int i=s;

         int j=m+1;

         int k=s;

         while(i<=m && j<=t)

             if(start[i]<=start[j])          //取start[i]和start[j]的最小者放入result[k]

                 result[k++]=start[i++];

             else

                 result[k++]=start[j++];

         if(i<=m)        //第一个序列没有遍历完

             while(i<=m)

                 result[k++]=start[i++];

         else            //第二个序列没有遍历完

             while(j<=t)

                 result[k++]=start[j++];

     }

     //一趟排序,h为序列长度

     public static void mergePass(int[] start,int[] result,int n,int h){

         int i=0;

         while(i<=n-2*h+1){

             merge(start,result,i,i+h-1,i+2*h-1);

             i+=2*h;

         }

         if(i<n-h+1)

             merge(start,result,i,i+h-1,n);

         else

             for(int k=i;k<=n;k++)

                 result[k]=start[k];

     }

     //归并排序

     public static void mergeSort(int[] start,int n){

         int h=1;

         int[] result=new int[n+1];

         while(h<n){

             mergePass(start, result, n, h);

             h=2*h;

             mergePass(result, start, n, h);

             h=2*h;

         }

     }

     //去掉数组中重复的部分

     public static void removeSame(int[] a){

         int min=a[0]-1;                    //把数组中的重复部分设置为min

         for(int i=0;i<a.length;){

             int j=i+1;

             while(j<a.length && a[i]==a[j]){

                 a[j]=min;

                 j++;

             }

             i=j;

         }//for

     }

 }