Java 归并排序算法

最后修改时间：2025 年 4 月 16 日

排序算法简介

算法是解决问题或执行计算的逐步过程。排序算法按特定顺序排列元素，通常是数字或按字典顺序排列。高效排序对于优化其他算法至关重要。

常见的排序算法包括

气泡排序
选择排序
插入排序
归并排序
快速排序
堆排序

归并排序概述

归并排序是一种分而治之的算法，它递归地将输入拆分为更小的子数组，对它们进行排序，然后将它们合并在一起。在所有情况下，它的时间复杂度均为 O(n log n)，使其对于大型数据集非常有效。

基本的归并排序实现

这是一个基本的归并排序实现，用于按升序排列整数

MergeSort.java

package com.zetcode;

import java.util.Arrays;

public class MergeSort {

    public static void mergeSort(int[] array) {
        if (array.length > 1) {
            int mid = array.length / 2;
            int[] left = Arrays.copyOfRange(array, 0, mid);
            int[] right = Arrays.copyOfRange(array, mid, array.length);
            
            mergeSort(left);
            mergeSort(right);
            
            merge(array, left, right);
        }
    }
    
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
    
    public static void main(String[] args) {

        int[] numbers = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Before sorting: " + Arrays.toString(numbers));
        
        mergeSort(numbers);
        System.out.println("After sorting: " + Arrays.toString(numbers));
    }
}

此实现演示了经典的归并排序方法。该数组被递归地分成两半，直到达到单个元素的基准情况。然后，合并操作将排序后的两半组合在一起。

对文本数据进行排序

归并排序还可以按字典顺序对字符串进行排序。这是一个按升序对字符串进行排序的实现

StringMergeSort.java

package com.zetcode;

import java.util.Arrays;

public class StringMergeSort {

    public static void mergeSort(String[] array) {
        if (array.length > 1) {
            int mid = array.length / 2;
            String[] left = Arrays.copyOfRange(array, 0, mid);
            String[] right = Arrays.copyOfRange(array, mid, array.length);
            
            mergeSort(left);
            mergeSort(right);
            
            merge(array, left, right);
        }
    }
    
    private static void merge(String[] result, String[] left, String[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i].compareTo(right[j]) <= 0) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
    
    public static void main(String[] args) {

        String[] words = {"apple", "orange", "banana", "pear", "kiwi"};
        System.out.println("Before sorting: " + Arrays.toString(words));
        
        mergeSort(words);
        System.out.println("After sorting: " + Arrays.toString(words));
    }
}

字符串版本使用 compareTo 方法进行字典比较。该算法的结构与数值版本相同，只有比较操作发生了变化。

降序排序

要按降序排序，我们只需反转合并步骤中的比较条件。以下是如何修改数值归并排序以进行降序排列

DescendingMergeSort.java

package com.zetcode;

import java.util.Arrays;

public class DescendingMergeSort {

    public static void mergeSort(int[] array) {
        if (array.length > 1) {
            int mid = array.length / 2;
            int[] left = Arrays.copyOfRange(array, 0, mid);
            int[] right = Arrays.copyOfRange(array, mid, array.length);
            
            mergeSort(left);
            mergeSort(right);
            
            merge(array, left, right);
        }
    }
    
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] >= right[j]) {  // Changed comparison operator
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
    
    public static void main(String[] args) {

        int[] numbers = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Before sorting: " + Arrays.toString(numbers));
        
        mergeSort(numbers);
        System.out.println("After sorting: " + Arrays.toString(numbers));
    }
}

唯一需要更改的是 merge 方法中的比较运算符，从 <= 更改为 >=。这种小的修改完全颠倒了排序顺序。

通用归并排序实现

我们可以创建一个适用于任何 Comparable 类型的通用版本，从而使代码更具可重用性。以下是如何实现通用归并排序

GenericMergeSort.java

package com.zetcode;

import java.util.Arrays;

public class GenericMergeSort<T extends Comparable<T>> {

    public void mergeSort(T[] array) {
        if (array.length > 1) {
            int mid = array.length / 2;
            T[] left = Arrays.copyOfRange(array, 0, mid);
            T[] right = Arrays.copyOfRange(array, mid, array.length);
            
            mergeSort(left);
            mergeSort(right);
            
            merge(array, left, right);
        }
    }
    
    private void merge(T[] result, T[] left, T[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i].compareTo(right[j]) <= 0) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
    
    public static void main(String[] args) {

        // Test with integers
        Integer[] numbers = {38, 27, 43, 3, 9, 82, 10};
        GenericMergeSort<Integer> intSorter = new GenericMergeSort<>();
        intSorter.mergeSort(numbers);
        System.out.println("Sorted numbers: " + Arrays.toString(numbers));
        
        // Test with strings
        String[] words = {"apple", "orange", "banana", "pear", "kiwi"};
        GenericMergeSort<String> stringSorter = new GenericMergeSort<>();
        stringSorter.mergeSort(words);
        System.out.println("Sorted words: " + Arrays.toString(words));
    }
}

这种通用实现可以对任何实现 Comparable 接口的对象数组进行排序。它可以用于数值和文本数据，而无需修改。

归并排序与快速排序基准测试

归并排序和快速排序都是高效的 O(n log n) 算法，但它们具有不同的特性。让我们通过一个简单的基准测试来比较它们的性能

SortBenchmark.java

package com.zetcode;

import java.util.Arrays;
import java.util.Random;

public class SortBenchmark {

    public static void main(String[] args) {

        int size = 1000000;
        int[] numbers = generateRandomArray(size);
        int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);
        
        // Merge sort benchmark
        long startTime = System.currentTimeMillis();
        mergeSort(numbers);
        long mergeSortTime = System.currentTimeMillis() - startTime;
        
        // Quick sort benchmark
        startTime = System.currentTimeMillis();
        Arrays.sort(numbersCopy);  // Uses dual-pivot quick sort
        long quickSortTime = System.currentTimeMillis() - startTime;
        
        System.out.println("Merge sort time: " + mergeSortTime + " ms");
        System.out.println("Quick sort time: " + quickSortTime + " ms");
    }
    
    private static int[] generateRandomArray(int size) {
        Random random = new Random();
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt();
        }
        return array;
    }

    public static void mergeSort(int[] array) {
        if (array.length > 1) {
            int mid = array.length / 2;
            int[] left = Arrays.copyOfRange(array, 0, mid);
            int[] right = Arrays.copyOfRange(array, mid, array.length);
            
            mergeSort(left);
            mergeSort(right);
            
            merge(array, left, right);
        }
    }
    
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }    
}

该示例对两种排序算法（归并排序和快速排序）进行基准测试。它生成一个随机整数数组，复制它，并测量使用 mergeSort（自定义实现）和 Java 内置 Arrays.sort（使用双轴快速排序）对每个数组进行排序所花费的时间。然后，该程序输出每种算法所花费的时间。此比较突出了两种不同排序技术在大型数据集上的性能，同时展示了如何在 Java 中准确测量执行时间。

归并排序和快速排序之间的主要区别

归并排序是稳定的（保持相等元素的顺序）
快速排序通常具有更好的常数因子（在实践中更快）
归并排序需要 O(n) 额外的空间
快速排序具有最坏情况 O(n²) 时间（虽然通过良好的枢轴选择很少见）
Java 的 Arrays.sort 对基元使用经过调整的快速排序

来源

Java 数组文档

在本教程中，我们介绍了 Java 中的归并排序算法，包括按升序和降序排列的数值和文本数据的实现。我们还通过一个简单的基准测试比较了归并排序和快速排序。

作者

我叫 Jan Bodnar，是一位经验丰富的程序员。我于 2007 年开始撰写编程文章，至今已撰写了 1400 多篇文章和 8 本电子书。凭借超过八年的教学经验，我致力于分享我的知识并帮助他人掌握编程概念。

列出所有Java教程。