java数据结构和算法——归并排序算法

一、归并排序介绍

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

二、归并排序算法的思路分析图

三、归并排序算法的应用示例需求

arr={8,4,5,7,1,3,6,2},请使用归并排序完成数组的排序。

四、归并排序算法的示例

1、代码

package com.rf.springboot01.dataStructure.sort;

import java.util.Arrays;

/**
 * @description: 归并排序示例
 * @author: xiaozhi
 * @create: 2020-08-11 21:11
 */
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];//递归需要一个额外的临时中转数组
        splitMerge(arr,0,arr.length-1,temp);
        System.out.println("归并排序后的数组："+Arrays.toString(arr));
    }
    /** 
    * @Description: 分解+合并方法
    * @Param:  arr 排序的原始数组
     *          left  左边初始索引
     *          right 右边末尾索引
     *          temp 临时的中转数组
    * @Author: xz  
    * @return: 
    * @Date: 2020/8/11 22:54  
    */
    public static void  splitMerge(int[] arr, int left,int right,int[] temp){
        if(left