合并排序(归并排序)代码-及实现

已80,20,6,45,35,19,100,64为例,

合并排序.jpg

JAVA实现代码

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{80,20,6,45,35,19,100,64};
        int left = 0;
        int right=arr.length-1;
        int[] tem = Arrays.copyOf(arr,arr.length);
        print(arr);
        mergeSort(arr,left,right,tem);
        print(arr);
    }

    public static void mergeSort(int[] arr , int left ,int right , int[] tem){
        if(right-left<1){
            return;
        }
        int mid = left + (right-left)/2;
        mergeSort(arr,left,mid,tem);
        mergeSort(arr,mid+1,right,tem);
        merge(arr,left,mid,right,tem);
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] tem) {
        int index=0;
        int l=left,r=mid+1;
        while(l<=mid && r<=right){
            if(arr[l]<arr[r]){
                tem[index++]=arr[l++];
            }else{
                tem[index++]=arr[r++];
            }
        }
        while(l<=mid){
            tem[index++]=arr[l++];
        }
        while(r<=right){
            tem[index++]=arr[r++];
        }

        for(int i=0;i<(right-left+1);i++){
            arr[left+i]=tem[i];
        }
    }


    private static void print(int[] arr){
        for (int i : arr){
            System.out.print(i+"\t");
        }
        System.out.println();
    }
}

代码执行过程

合并过程.png

作者QQ：420318184
邮箱:fy@0fy0.com