归并排序

分析

代码

package 算法;

import java.util.Arrays;

public class 归并排序 {

    public static void main(String[] args) {
        int[] nums = new int[]{6,2,1,5,3,4,9,8};
        int[] temp = new int[nums.length];
        sort(nums, 0,nums.length-1, temp);
        System.out.println(Arrays.toString(nums));
    }
    private static void sort(int[] arr,int left,int right,int[] temp){
        if(left<right){
            int mid = (left+right)/2;
            //对左半边进行归并排序
            sort(arr, left, mid,temp);
            //对右半边进行归并排序
            sort(arr, mid+1, right,temp);
            //开始分治中的治操作，在归的途中进行合并
            merge(arr,left,mid,right,temp);
        }
    }

    private static void merge(int[] arr,int left,int mid,int right,int[] temp) {
        //左分支的指针
        int i = left;
        //右分支的指针
        int j = mid+1;
        //temp数组的指针
        int index = 0;
        //在左右两分支找最小的数放在temp数组中
        while(i<=mid&&j<=right){
            //找那边更小，找到指针也需要移动
            if(arr[i]<arr[j]){
                temp[index++] = arr[i++];
            }else{
                temp[index++] = arr[j++];
            }
        }
        //找完将剩余元素之间放入temp中
        while(i<=mid){
            temp[index++] = arr[i++];
        }
        while(j<=right){
            temp[index++] = arr[j++];
        }
        //最后将temp复制回原数组
        index=0;
        while(left<=right){
            arr[left++]=temp[index++];
        }
    }
}