Java归并排序怎么实现

Java归并排序是一种采用分治法（Divide and Conquer）的排序算法，它将一个序列（list）分为两个子序列（sub-lists），然后对子序列进行排序，最后将排序好的子序列合并成一个有序序列。归并排序的思想就是分而治之，它的主要步骤如下：

（1）将序列每次折半划分，直到划分后的子序列只含有一个元素或者为空；

（2）将子序列两两合并，合并时对元素进行比较，并按照升序或者降序排列；

（3）重复（1）（2）步，直到合并成一个序列，即得到有序序列。

下面给出一个Java实现的归并排序算法的代码：

public void mergeSort(int[] nums) {
    int[] temp = new int[nums.length];
    mergeSort(nums, 0, nums.length - 1, temp);
}

public void mergeSort(int[] nums, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left + right) / 2;
        // 左边归并排序，使得左子序列有序
        mergeSort(nums, left, mid, temp);
        // 右边归并排序，使得右子序列有序
        mergeSort(nums, mid + 1, right, temp);
        // 将两个有序子数组合并操作
        merge(nums, left, mid, right, temp);
    }
}

public void merge(int[] nums, int left, int mid, int right, int[] temp) {
    int i = left; // 左序列指针
    int j = mid + 1; // 右序列指针
    int t = 0; // 临时数组指针
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[t++] = nums[i++];
        } else {
            temp[t++] = nums[j++];
        }
    }
    while (i <= mid) { // 将左边剩余元素填充进temp中
        temp[t++] = nums[i++];
    }
    while (j <= right) { // 将右序列剩余元素填充进temp中
        temp[t++] = nums[j++];
    }
    t = 0;
    // 将temp中的元素全部拷贝到原数组中
    while (left <= right) {
        nums[left++] = temp[t++];
    }
}

以上就是Java归并排序的实现，它的时间复杂度为O（nlogn），空间复杂度为O（n），是一种高效的排序算法。