基础排序算法之归并排序

归并排序同快排一样，都是贯彻了分治思想，不同的是归并排序需要借助一个长度和待排序数组一样的空数组来完成排序操作

package com.scaler7.sort;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {11,44,23,67,88,65,34,48,9,12};
        int[] tmp = new int[arr.length];    //新建一个临时数组存放
        mergeSort(arr);
        for(int i=0;i=r)
            return;
        int mid=(l+r)/2;
        // 数组中的元素不止一个时，将它从中间分为分为左右两段，并递归地分割，直至数组中只剩一个元素，然后返回上层调用函数，执行merge
        mergeSort(arr,l,mid,temp);
        mergeSort(arr,mid+1,r,temp);
        merge(arr,l,mid,r,temp);

    }

    
    private static void merge(int[] arr, int l, int mid, int r, int[] temp) {
        // 定义i，j分别为左数组起点和右数组起点
        int i=l,j=mid+1;
        // t为temp的起点
        int t=0;
        // 执行循环，直至左右两个数组其中一个遍历完成
        while(i<=mid && j<=r){
            // 比较左右两个数组的每个数
            if(arr[i]>=arr[j]){
                // 如果右边数组中的数较小，将它插入temp中，并将temp指针和右边数组指针都后移一位
                temp[t++]=arr[j++];
            }else{
                // 如果左边数组中的数较小，将它插入temp中，并将temp指针和左边数组指针都后移一位
                temp[t++]=arr[i++];
            }
        }

        // 执行完上面的操作之后，此时肯定会有一个数组还没有遍历完成，那么将它剩下的数直接插入到temp中
        while(i<=mid){
            temp[t++]=arr[i++];
        }
        while(j<=r){
            temp[t++]=arr[j++];
        }
        // temp指针向前移动一位，防止数组越界
        t--;
        // 将temp中的值覆盖至arr中
        while(r>=l){
            arr[r--]=temp[t--];
        }
    }

}