归并排序Java实现

### 回答1：
归并排序是一种分治算法，它将一个数组（或列表）分成两半，将两半分别排序，然后将排序后的两半合并起来。这是一种稳定的排序算法。

Java 代码如下：

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + (r - l) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static void merge(int[] arr, int l, int mid, int r) {
        int[] temp = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r) {
            temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            temp[i++] = arr[p1++];
        }
        while (p2 <= r) {
            temp[i++] = arr[p2++];
        }
        for (i = 0; i < temp.length; i++) {
            arr[l + i] = temp[i];
        }
    }
}

希望这个示例能帮到你。

### 回答2：
归并排序是一种常见的排序算法，采用分治的思想来进行排序。在Java中，可以通过递归来实现归并排序。

首先，创建一个mergeSort()方法来进行归并排序。这个方法接收一个待排序的数组作为参数，并返回一个已经排好序的数组。代码如下：

public static int[] mergeSort(int[] arr) {
    // 递归终止条件：数组长度小于等于1时，不需要排序，直接返回
    if (arr.length <= 1) {
        return arr;
    }

    // 将原始数组分为两部分
    int mid = arr.length / 2;
    int[] left = new int[mid];
    int[] right = new int[arr.length - mid];
    System.arraycopy(arr, 0, left, 0, mid);
    System.arraycopy(arr, mid, right, 0, arr.length - mid);

    // 递归调用mergeSort()方法对左右两部分数组进行排序
    left = mergeSort(left);
    right = mergeSort(right);

    // 合并左右两部分排序后的数组
    return merge(left, right);
}

接下来，创建一个merge()方法来合并两个已经排序好的数组。代码如下：

public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int leftIndex = 0;
    int rightIndex = 0;
    int resultIndex = 0;

    // 比较左右两个数组的元素，将较小的元素放入结果数组中
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] <= right[rightIndex]) {
            result[resultIndex++] = left[leftIndex++];
        } else {
            result[resultIndex++] = right[rightIndex++];
        }
    }

    // 将剩余的元素放入结果数组
    while (leftIndex < left.length) {
        result[resultIndex++] = left[leftIndex++];
    }
    while (rightIndex < right.length) {
        result[resultIndex++] = right[rightIndex++];
    }

    return result;
}

最后，通过调用mergeSort()方法来对待排序的数组进行排序。例如：

public static void main(String[] args) {
    int[] arr = {4, 2, 6, 1, 9, 3};
    int[] sortedArr = mergeSort(arr);
    System.out.println(Arrays.toString(sortedArr));
}

以上就是归并排序的Java实现。该算法的时间复杂度为O(nlogn)，其中n为数组的长度。

### 回答3：
归并排序是一种经典的排序算法，它采用分治的思想，将待排序的数组递归地分成两部分，然后将这两部分分别排序，最后将排好序的两部分合并成一个有序的数组。

在Java中实现归并排序可以采用以下步骤：

1. 定义一个方法 mergeSort，参数为待排序的数组和数组的开始索引和结束索引。
2. 如果开始索引小于结束索引，则继续进行排序操作。
3. 计算数组的中间索引，即 (开始索引+结束索引)/2。
4. 分别调用 mergeSort 方法对数组的前半部分和后半部分进行排序，即 mergeSort(arr, start, mid) 和 mergeSort(arr, mid+1, end)。
5. 定义一个 merge 方法，参数为待合并的数组、开始索引、中间索引和结束索引。
6. 创建两个临时数组，分别存储待合并的两个数组的元素。
7. 初始化两个指针，分别指向两个临时数组的开头。
8. 使用一个循环，比较两个指针所指向的元素大小，将较小的元素放入原数组中，并移动指针到下一个位置。
9. 如果某个指针越界，则将另一个临时数组中的剩余元素放入原数组中。
10. 返回合并后的数组。
11. 在 mergeSort 方法中，调用 merge 方法将排好序的前半部分和后半部分进行合并，并返回合并后的数组。
12. 最后，在主函数中调用 mergeSort 方法对待排序的数组进行排序。

通过以上步骤，我们可以实现归并排序的Java代码。归并排序的时间复杂度为 O(nlogn)，具有稳定性，适用于大规模数据的排序。