题解 | #排序#

• 重写了归并排序，刚好复习排序算法，开始先创建一个辅助数组，提高效率

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        int[] aux = new int[arr.length];
        mergeSort(arr, aux, 0, arr.length - 1);
        return arr;
    }
    private void mergeSort(int[] arr, int[] aux, int lo, int hi)
    {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(arr, aux, lo, mid);
        mergeSort(arr, aux, mid + 1, hi);
        // 合并
        merge(arr, aux, lo, mid, hi);
    }
    private void merge(int[] arr, int[] aux, int lo, int mid, int hi)
    {
        for (int i = lo; i <= hi; i++)
        {
            aux[i] = arr[i];
        }
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++)
        {
            if      (i > mid)         arr[k] = aux[j++];
            else if (j > hi)          arr[k] = aux[i++];
            else if (aux[i] < aux[j]) arr[k] = aux[i++];
            else                      arr[k] = aux[j++];
        }
    }
}