排序算法-归并排序（Java）

package com.rao.sort;import java.util.Arrays;/** * @author Srao * @className MergeSort * @date 2019/12/7 10:24 * @package com.rao.sort * @Description 归并排序 */public class MergeSort {    /**     * 归并排序：递归写法     * @param arr：要排序的数组     * @param left：数组最左边的元素的下标     * @param right：数组最右边的元素的下标     */    public static int[] mergeSort(int[] arr, int left, int right){        //如果left == right,那么说明数组中只有一个元素了        if (left < right){            int mid = (left + right) / 2;            arr = mergeSort(arr, left, mid);//对左边的部分进行归并排序            arr = mergeSort(arr, mid+1, right);//对右边的部分进行归并排序            merge(arr, left, mid, right);//将上面两部分进行合并，变成一个有序的数组        }        return arr;    }    /**     * 归并排序：非递归写法     * @param arr：要排序的数组     * @return     */    public static int[] mergeSort2(int[] arr){        int n = arr.length;        //分组时每一轮数组的长度为1，2，4，8，16....        for (int i = 1; i < n; i = i+i){            int left = 0;            int mid = left + i - 1;            int right = mid + i;            while (right < n){                merge(arr, left, mid, right);                left = right + 1;                mid = left + i -1;                right = mid + i;            }            //每一次分组合并之后可能会有多余的数组，不够2，4，8...，要把他们也合并到数组里面来            if (left < n && mid < n){                merge(arr, left, mid, n-1);            }        }        return arr;    }    /**     * 对数组进行合并     * @param arr：要操作的数组     * @param left：从left到right之间进行合并     * @param mid     * @param right     */    private static void merge(int[] arr, int left, int mid, int right) {        int i = left;//左边部分的起始下标        int j = mid+1;//右边部分的起始下标        int k = 0;//新数组的下标，新数组用来存放排好序的数字        int[] a = new int[right-left+1];//新数组        while (i <= mid && j <= right){            if (arr[i] < arr[j]){                a[k] = arr[i];                k++;                i++;            }else if (arr[i] >= arr[j]){                a[k] = arr[j];                k++;                j++;            }        }        //把没有排序的数字放入新数组        while (i <= mid){            a[k] = arr[i];            k++;            i++;        }        while (j <= right){            a[k] = arr[j];            k++;            j++;        }        //把新数组中的数字覆盖到旧数组中        for (int m = 0; m < a.length; m++){            arr[left+m] = a[m];        }    }    public static void main(String[] args) {        int[] arr = {3, 6, 9, 5, 0};        System.out.println(Arrays.toString(arr));        arr = mergeSort(arr, 0, arr.length-1);        System.out.println(Arrays.toString(arr));        int[] arr2 = {3, 6, 9, 5, 0};        System.out.println(Arrays.toString(arr2));        arr2 = mergeSort2(arr);        System.out.println(Arrays.toString(arr2));    }}

归并排序的思想：

把数组一分为二，对左右两边分别进行归并排序，一直往下递归，直到数组不能再分，此时数组中只有一个元素，且一个元素是有序的，再把左右两部分进行合并，一直递归合并成一个有序数组。