归并排序(分治思想)

分治法将问题分成一些小的问题然后递归求解,治就是一个合的思想。

分治_百度百科

分其实就是把一个数组从中间分成两个数组,左数组和右数组,分界点为mid=left+right/2,然后递归,最后得到上图所示蓝色字体的最后一行一个个单独的数组

治(合并)就是要求两个分好的数组进行按照一定规则的排序,这时我们使用三个指针来完成其操作,第一个left(i)指针是指向左数组的首节点,第二个指针mid+1(j)指向右数组的首节点,第三个指针temp[0](t)指向新建数组的首节点

import java.util.Arrays;

public class GuibingMergesort {
    public static void main(String[] args) {
        int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 };
        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