java 实现一个归并排序

归并排序是一种经典的排序算法，它的基本思想是将待排序的序列不断地划分成更小的子序列，直到每个子序列只有一个元素，然后再将这些子序列两两合并，直到最终得到一个有序的序列。

在Java中实现归并排序可以按照以下步骤进行：

1. 首先，定义一个递归函数mergeSort，该函数用于将待排序的数组划分成更小的子数组，并进行合并排序。

2. 在mergeSort函数中，首先判断数组的长度是否大于1，如果小于等于1，则无需排序，直接返回。

3. 如果数组长度大于1，则将数组划分成两个子数组，分别调用mergeSort函数对这两个子数组进行排序。

4. 接下来，定义一个merge函数，用于将两个已经排好序的子数组合并成一个有序的数组。

5. 在merge函数中，创建一个临时数组，用于存放合并后的结果。同时定义两个指针i和j，分别指向两个子数组的起始位置。

6. 比较两个子数组中的元素大小，将较小的元素放入临时数组中，并将对应指针后移一位。

7. 当其中一个子数组的元素全部放入临时数组后，将另一个子数组中剩余的元素依次放入临时数组中。

8. 最后，将临时数组中的元素复制回原数组的对应位置。

下面是Java代码实现归并排序的示例：

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (int m = 0; m < temp.length; m++) {
            arr[left + m] = temp[m];
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 1};
        mergeSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}