Java 归并排序算法图解与实现

核心原理

归并排序（MERGE-SORT）的核心在于经典的“分而治之”策略：

• 分（Divide）：将当前区间平均切分，直至每个子序列仅含一个元素（天然有序）。
• 治（Conquer）：将相邻的两个有序子序列合并为一个更大的有序序列，依次回溯。

该过程的结构类似完全二叉树，递归深度为 $log_2n$。在实际实现中，通常优先选择递归方式，其逻辑更直观地展现了分治的过程。

合并操作详解

归并的关键步骤是将两个已经有序的子数组合并为一个有序序列。例如，将 [4,5,7,8] 和 [1,2,3,6] 合并为 [1,2,3,4,5,6,7,8]。

具体执行过程如下：

1. 设置三个指针：i 指向左子序列起点，j 指向右子序列起点，t 指向辅助数组起点。
2. 比较 arr[i] 和 arr[j]，将较小值放入辅助数组，并将对应指针后移。
3. 当某一边遍历完毕后，直接将另一边剩余元素全部拷贝至辅助数组。
4. 最后将辅助数组的内容覆盖回原数组指定范围。

Java 代码实现

为了避免在递归过程中频繁开辟空间导致性能下降，建议在排序前预先分配一个与原数组等长的临时辅助数组。

package sortdemo;

import java.util.Arrays;

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

    /**
     * 对外提供的接口方法
     */
    public static void sort(int []arr){
        // 预分配长度等于原数组的临时数组
        int []temp = new int[arr.length]; 
        sort(arr,0,arr.length-1,temp);
    }

    /**
     * 递归排序主逻辑
     */
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            // 左边归并排序
            sort(arr,left,mid,temp); 
            // 右边归并排序
            sort(arr,mid+1,right,temp); 
            // 合并两个有序子序列
            merge(arr,left,mid,right,temp); 
        }
    }

    /**
     * 合并操作
     */
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;      // 左序列指针
        int j = mid+1;     // 右序列指针
        int t = 0;         // 临时数组指针

        // 左右两边都有数据时，按大小填入临时数组
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }

        // 处理左边剩余元素
        while(i<=mid){
            temp[t++] = arr[i++];
        }
        // 处理右边剩余元素
        while(j<=right){
            temp[t++] = arr[j++];
        }

        // 将辅助数组拷贝回原数组
        t = 0;
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}

结果验证

上述代码对 {9,8,7,6,5,4,3,2,1} 进行排序，最终执行结果如下：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

总结

归并排序是一种高效的稳定排序算法，其最好、最坏和平均时间复杂度均为 $O(nlogn)$。每次合并操作的平均复杂度为 $O(n)$，结合完全二叉树的深度 $log_2n$，总计算量控制在极优水平。 值得注意的是，Java 中 java.util.Arrays.sort() 采用的 TimSort 算法，正是对归并排序的进一步优化版本。

以上就是 Java 归并排序算法的详细内容，更多关于 Java 排序算法的资料请关注本站其它相关文章！