java实现归并排序-归并排序代码实现的排序思想示意图（merge-sort排序）

目录

归并排序介绍

归并排序（merge-sort）是利用归并的思想实现的排序方法java实现归并排序，该算法采用经典的分治（divide-and-conquer）策略 (分治法将问题分（divide）成一些小的问题然后递归求解，而治（conquer）的阶段则将分的阶段得到的各答案修补在一起java实现归并排序，即分而治之）。

归并排序思想示意图

归并排序代码实现

package com.atschool.sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class MergeSort {
    public static void main(String[] args) {
 /*       int[]  arr ={8,4,5,7,1,3,6,2};
        int[] temp =new int[arr.length];
        System.out.println("归并排序前：" + Arrays.toString(arr));
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println("归并排序后：" + Arrays.toString(arr));*/
        int[] arr = new int [80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] =(int)(Math.random()*80000);//生产一个[0,800000)的数
        }
        int[] temp =new int[arr.length];
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("归并排序前的时间" +date1Str);
        //测试选择排序
        mergeSort(arr,0,arr.length-1,temp);
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("归并排序后的时间" +date2Str);
    }
    public  static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left < right){
            int mid =(left+right)/2; //中间索引
            //向左递归进行分解
            mergeSort(arr,left,mid,temp);
            //向右递归进行分解
            mergeSort(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; //初始化i，左边有序序列的初始索引
        int j =mid+1;//初始化j,右边有序序列的初始索引
        int t =0;//指向temp数组的当前索引
        //一
        //先把左右两边（有序）的数据按照规则填充到temp数组，直到左右两边的有序序列，有一边处理完毕为止
        while(i<=mid && j<=right){
            //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素，即将左边的当前元素，填充到temp数组
            if(arr[i] <=arr[j]){
                temp[t] =arr[i];
                t+=1;
                i+=1;
            } else{//反之，将右边有序序列的当前元素，填充到temp数组
                temp[t] =arr[j];
                t+=1;
                j+=1;
            }
        }
        //二
        //把有剩余数据的一边的数据依次全部填充到temp
        while(i<=mid){//左边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] =arr[i];
            t+=1;
            i+=1;
        }
        while(j<=right){//右边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] =arr[j];
            t+=1;
            j+=1;
        }
        //三
        //将temp数组的元素拷贝到arr
        //注意，并不是每次都拷贝所有
        t=0;
        int tempLeft =left;
        //第一次合并 tempLeft =0,right=1 //tempLeft =2 right =3//tempLeft =0 right=3
        //最后一次 tempLeft =0 right =7
        while(tempLeft <=right){
            arr[tempLeft] =temp[t];
            t+=1;
            tempLeft+=1;
        }
    }
}