归并排序

归并排序的示意图1   基本思想

归并排序的示意图2  合并有序子序列

分解和合并代码如下

将两个有序子序列合并

 public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i=left;//左边数组初始索引
        int j=mid+1;//右边数组初始索引
        int t=0;
        //有序数组转移到temp,直到左右两边有一边数组完成转移
        while (i<=mid&&j<=right){
            if(arr[i]<arr[j]){
                temp[t]=arr[i];
                t++;
                i++;
            }else {
                temp[t]=arr[j];
                t++;
                j++;
            }
        }
        //剩余的转移到temp
        //如果左边数组有剩余，则继续进行转移
        while (i<=mid){
            temp[t]=arr[i];
            t++;
            i++;
        }
        //如果右边数组有剩余，则继续进行转移
        while (j<=right){
            temp[t]=arr[j];
            t++;
            j++;
        }
        //temp数组转移到arr;
        t=0;
        while (left<=right){
            arr[left]=temp[t];
            t++;
            left++;
        }

    }

采用递归的方法对数组进行分解

public static void mergesort(int[] arr,int left,int right,int[] temp){
        if(left>=right){
            return;
        }
        int mid=left+(right-left)/2;
        //向左递归进行分解
        mergesort(arr,left,mid,temp);
        //向右递归进行分解
        mergesort(arr,mid+1,right,temp);
        //合并两个有序数组
        merge(arr,left,mid,right,temp);

    }

完整代码如下

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr={8,4,5,7,1,3,6,2,10,-1,2000,10,7,8};
        int[] temp=new int[arr.length];
        mergesort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));

    }
    //分解+合并
    public static void mergesort(int[] arr,int left,int right,int[] temp){
        if(left>=right){
            return;
        }
        int mid=left+(right-left)/2;
        //向左递归进行分解
        mergesort(arr,left,mid,temp);
        //向右递归进行分解
        mergesort(arr,mid+1,right,temp);
        //合并两个有序数组
        merge(arr,left,mid,right,temp);

    }
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i=left;//左边数组初始索引
        int j=mid+1;//右边数组初始索引
        int t=0;
        //有序数组转移到temp,直到左右两边有一边数组完成转移
        while (i<=mid&&j<=right){
            if(arr[i]<arr[j]){
                temp[t]=arr[i];
                t++;
                i++;
            }else {
                temp[t]=arr[j];
                t++;
                j++;
            }
        }
        //剩余的转移到temp
        //如果左边数组有剩余，则继续进行转移
        while (i<=mid){
            temp[t]=arr[i];
            t++;
            i++;
        }
        //如果右边数组有剩余，则继续进行转移
        while (j<=right){
            temp[t]=arr[j];
            t++;
            j++;
        }
        //temp数组转移到arr;
        t=0;
        while (left<=right){
            arr[left]=temp[t];
            t++;
            left++;
        }

    }
}