归并排序的基本原理

归并排序基于分治法（Divide and Conquer）的思想，即把一个大问题分解为多个小问题来解决，再将各个小问题的解合并起来得到大问题的解。具体来说，归并排序的过程包括以下几个步骤：

1. 分解：将数组不断地对半分割，直到每个子数组只包含一个元素。这是因为单个元素的数组自然就是有序的。
2. 合并：将这些有序的小数组逐步合并成更大的有序数组，直到最终整个数组变成一个有序数组。

Java实现详解

主类与主方法

public class MergeSort {
    public static void main(String[] args){
        //先定义一个数组
        int[] a={3,2,1,4,5};
        mergeSort(a,0,a.length-1);
        System.out.println("排序后的数组为：");
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]);
        }

• 这里定义了一个名为 MergeSort 的类，其中包含 main 方法。
• 在 main 方法中，我们定义了一个待排序的整数数组 array。
• 调用 mergeSort 方法对数组进行排序，传入数组、数组的起始索引 0 和结束索引 array.length - 1。
• 最后，遍历数组并打印排序后的结果。

归并排序方法

//定义一个归并排序的方法
    public static void mergeSort(int[] a,int left,int right){
        if(left<right){
            //先找到中间点
            int mid = (left+right)/2;
            //对左边部分进行递归排序
            mergeSort(a,left,mid);
            //对右边部分进行递归排序
            mergeSort(a,mid+1,right);
            //合并两个有序数组
            merge(a,left,mid,right);
        }
    }

• mergeSort 是一个递归方法，它接受一个数组和两个索引（left 和 right），表示要排序的数组范围。
• 当 left 小于 right 时，说明这个范围内有超过一个元素，需要进一步分割。
• 计算中间索引 mid，将数组从中间一分为二。
• 递归调用 mergeSort 方法对左右两半部分分别进行排序。
• 排序完成后，调用 merge 方法将两个已排序的部分合并成一个有序数组。

合并方法

public static void merge(int[] array, 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 (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        // 如果左边子数组还有剩余，直接复制到临时数组
        while (i <= mid) {
            temp[k++] = array[i++];
        }

        // 如果右边子数组还有剩余，直接复制到临时数组
        while (j <= right) {
            temp[k++] = array[j++];
        }

        // 将临时数组中的元素复制回原数组
        for (int m = 0; m < temp.length; m++) {
            array[left + m] = temp[m];
        }
    }

• merge 方法负责将两个已排序的子数组合并成一个有序数组。
• 首先创建一个临时数组 temp，用于存放合并后的结果。
• 使用三个指针 i, j, k 分别指向左边子数组的起始位置、右边子数组的起始位置和临时数组的起始位置。
• 通过循环比较左右两个子数组的元素，将较小的元素放入临时数组 temp 中，并移动相应的指针。
• 如果左边或右边子数组有剩余元素，直接将其复制到临时数组 temp 中。
• 最后，将临时数组 temp 中的元素复制回原数组 array 中对应的位置。

总结：归并排序先将一个数组分成一个有一个的单个元素，然后再按步骤递归并调用合并方法对各个元素进行排序；是分解到最后一步之后，逐步向上合并，最后合并成完成的数组。