排序-归并排序

归并排序（Merge Sort）是一种分而治之的排序算法。它将数组分成两半，对每半部分递归地应用归并排序，然后将排序好的两半合并在一起。以下是归并排序的关键知识点和一个用Java实现的示例：

归并排序知识点

1. 分而治之：将问题分解成小问题，解决小问题，然后将解决的小问题合并起来，从而完成对整个问题的求解。
2. 递归：归并排序是一个典型的递归算法，它通过递归调用自身来分解数组。
3. 合并：合并两个已排序的数组（或数组的一部分）是归并排序的核心操作。
4. 时间复杂度：归并排序的最好、最坏和平均时间复杂度都是O(n log n)，其中n是数组的长度。
5. 空间复杂度：归并排序需要额外的空间来存储临时数组，因此其空间复杂度为O(n)。

Java实现

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

public class MergeSort {  
  
    // 主函数，用于对arr[l..r]范围进行归并排序  
    public static void sort(int[] arr, int l, int r) {  
        if (l < r) {  
            // 找到中间位置，分割数组  
            int m = l + (r - l) / 2;  
  
            // 递归排序两半  
            sort(arr, l, m);  
            sort(arr, m + 1, r);  
  
            // 合并两个有序数组  
            merge(arr, l, m, r);  
        }  
    }  
  
    // 合并两个有序数组arr[l..m]和arr[m+1..r]  
    private static void merge(int[] arr, int l, int m, int r) {  
        // 创建临时数组  
        int[] temp = new int[r - l + 1];  
  
        // 初始化两个指针  
        int i = l, j = m + 1;  
        int k = 0;  
  
        // 合并两个数组到temp中  
        while (i <= m && j <= r) {  
            if (arr[i] <= arr[j]) {  
                temp[k++] = arr[i++];  
            } else {  
                temp[k++] = arr[j++];  
            }  
        }  
  
        // 复制剩余的元素  
        while (i <= m) {  
            temp[k++] = arr[i++];  
        }  
  
        while (j <= r) {  
            temp[k++] = arr[j++];  
        }  
  
        // 将temp中的元素复制回arr  
        for (i = l, k = 0; i <= r; i++, k++) {  
            arr[i] = temp[k];  
        }  
    }  
  
    // 调用sort函数对arr进行排序  
    public static void sort(int[] arr) {  
        sort(arr, 0, arr.length - 1);  
    }  
  
    // 测试代码  
    public static void main(String[] args) {  
        int[] arr = {12, 11, 13, 5, 6, 7};  
        sort(arr);  
        for (int num : arr) {  
            System.out.print(num + " ");  
        }  
    }  
}

这个实现包含了归并排序的所有核心步骤：分解、递归排序和合并。sort函数是归并排序的入口点，它接受数组的起始和结束索引作为参数。merge函数负责将两个已排序的数组段合并成一个有序数组。最后，main函数提供了一个测试归并排序的示例。