2.4归并排序

2.4归并排序
时间复杂度o(n*logn)

思路：0~N-1 个数
1.将数组中的每个数成为长度为1的有序区间
2.将相邻有序区间长度为1的合并得到长度为2的有序区间
3.将相邻有序区间长度为2的合并得到长度为4的有序区间
.......
依次合并得到长度为N的有序区间

//归并排序
package chenzp;

import java.util.Scanner;

public class barrier2_5 {

public static int[] barrier(int[] A, int n) {
     sort(A,0,n-1);
       return A;
}

 public static void sort(int[] data,int left,int right){
     if(left<right){
         int middle=(left+right)/2;
         //划分左右
         sort(data,left,middle);
          sort(data,middle+1,right);
         //合并左右
         merge(data,left,middle,right);
     }
 }
  
 //合并左右两个子数组
 public static void merge(int[] data,int left,int middle,int right){
     //临时数组
     int[] tempArr=new int[right-left+1];
     //左边数组游标
     int leftIndex=left;
     //右边数据游标
     int rightIndex=middle+1;
     //临时数组游标
     int tempIndex=0;
      
     while(leftIndex<=middle&&rightIndex<=right){
         //临时数组选取左、右子数组中小数值
        if(data[leftIndex]<data[rightIndex]){
            tempArr[tempIndex++]=data[leftIndex++];
        }else{
            tempArr[tempIndex++]=data[rightIndex++];
        }
     }
     //剩余的直接放入
     while(leftIndex<=middle){
            tempArr[tempIndex++]=data[leftIndex++];
     }
     //剩余的直接放入
     while(rightIndex<=right){
            tempArr[tempIndex++]=data[rightIndex++];
     }
     //将临时数组放回原数组相应位置
     int temp=0;
     while((temp+left)<=right){
         data[left+temp]=tempArr[temp];
         temp++;
     }
 }

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a[] = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = sc.nextInt();
    }

    barrier2_5.barrier(a, n);

    for (int i : a) {
        System.out.println(i);
    }
}

}