// 归并排序算法, a是数组，n表示数组大小 public static void mergeSort(int[] a, int n) { mergeSortInternally(a, 0, n-1); } // 递归调用函数 private static void mergeSortInternally(int[] a, int p, int r) { // 递归终止条件 if (p >= r) return; // 取p到r之间的中间位置q int q = (p+r)/2; // 分治递归 mergeSortInternally(a, p, q); mergeSortInternally(a, q+1, r); // 将A[p...q]和A[q+1...r]合并为A[p...r] merge(a, p, q, r); } private static void merge(int[] a, int p, int q, int r) { int i = p; int j = q+1; int k = 0; // 初始化变量i, j, k int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组 // 1 排序 while (i<=q && j<=r) { if (a[i] <= a[j]) { tmp[k++] = a[i++]; // i++等于i:=i+1 } else { tmp[k++] = a[j++]; } } // 2 判断哪个子数组中有剩余的数据 int start = i; int end = q; if (j <= r) { start = j; end = r; } // 3 将剩余的数据拷贝到临时数组tmp while (start <= end) { tmp[k++] = a[start++]; } // 4 将tmp中的数组拷贝回a[p...r] for (i = 0; i <= r-p; ++i) { a[p+i] = tmp[i]; } }

这段代码是一个归并排序算法的实现。归并排序是一种分治算法，通过将待排序的数组不断地划分成更小的子数组，然后合并这些子数组来实现排序。

该代码中的`mergeSort`函数是对外的调用接口，它接受一个整型数组`a`和数组大小`n`作为参数，然后调用`mergeSortInternally`函数来进行递归排序。

`mergeSortInternally`函数是递归调用的实现部分，它接受一个整型数组`a`，起始位置`p`和结束位置`r`作为参数。在函数内部，首先判断递归终止条件，即当起始位置大于等于结束位置时，直接返回。然后找到起始位置和结束位置之间的中间位置`q`，然后分别递归调用`mergeSortInternally`函数对左右两个子数组进行排序。最后调用`merge`函数将排好序的子数组进行合并。

`merge`函数用于将两个已排好序的子数组合并为一个有序的数组。它接受一个整型数组`a`，起始位置`p`，中间位置`q`和结束位置`r`作为参数。在函数内部，首先创建一个临时数组`tmp`，它的大小与要合并的子数组大小相同。然后通过比较两个子数组中的元素大小，将较小的元素依次放入临时数组中。接着判断哪个子数组中还有剩余的元素，将剩余的元素拷贝到临时数组中。最后将临时数组中的元素拷贝回原数组`a`的相应位置，完成合并操作。

通过不断递归调用`mergeSortInternally`函数和合并操作，最终实现了对整个数组的排序。归并排序的时间复杂度为O(nlogn)。

相关问题

利用归并排序算法将读入的n个数从小到大排序后输出。 （C++选手请不要试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。） 本题为函数题，只需要提交函数即可 c/c++： void MergeSort(int[] a,int l,int r) { } java： public static void MergeSort(int[] a,int l,int r) { }

归并排序是一种常见的排序算法，它的核心思想是将一个数组分成两个子数组，分别对子数组进行排序，然后将两个有序的子数组合并成一个有序的数组。下面是一个 C++ 的归并排序实现：

void merge(int a[], int l, int mid, int r) {
    int n1 = mid - l + 1;
    int n2 = r - mid;
    int left[n1], right[n2];
    for (int i = 0; i < n1; i++) {
        left[i] = a[l + i];
    }
    for (int i = 0; i < n2; i++) {
        right[i] = a[mid + 1 + i];
    }
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            a[k++] = left[i++];
        } else {
            a[k++] = right[j++];
        }
    }
    while (i < n1) {
        a[k++] = left[i++];
    }
    while (j < n2) {
        a[k++] = right[j++];
    }
}

void MergeSort(int a[], int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = l + (r - l) / 2;
    MergeSort(a, l, mid);
    MergeSort(a, mid + 1, r);
    merge(a, l, mid, r);
}

在 `merge` 函数中，我们需要先将数组分成两个子数组 `left` 和 `right`，然后将它们按照从小到大的顺序合并成一个有序的数组。在 `MergeSort` 函数中，我们将数组分成两个子数组，分别对它们进行排序，然后再将它们合并起来。递归的基本情况是当子数组的长度为 1 或 0 时，它们已经有序了，无需排序。

下面是一个 Java 的归并排序实现：

public static void merge(int[] a, int l, int mid, int r) {
    int n1 = mid - l + 1;
    int n2 = r - mid;
    int[] left = new int[n1];
    int[] right = new int[n2];
    for (int i = 0; i < n1; i++) {
        left[i] = a[l + i];
    }
    for (int i = 0; i < n2; i++) {
        right[i] = a[mid + 1 + i];
    }
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            a[k++] = left[i++];
        } else {
            a[k++] = right[j++];
        }
    }
    while (i < n1) {
        a[k++] = left[i++];
    }
    while (j < n2) {
        a[k++] = right[j++];
    }
}

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

同样地，这个算法的时间复杂度是 $O(n\log n)$，其中 $n$ 是数组的长度。

用Java编码归并排序， 利用归并排序算法将读入的n个数从小到大排序后输出。

好的，下面是Java代码实现归并排序并对n个数进行排序：

import java.util.Scanner;

public class MergeSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        mergeSort(arr, 0, n - 1);
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

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

代码中的mergeSort方法实现归并排序，merge方法实现归并操作。首先读入n个数，然后调用mergeSort方法进行排序，最后输出排好序的数组。