Java 中的归并排序算法 - 完整教程及源代码

算法原理

归并排序算法的原理实现可以参考维基百科Merge sort，用于对包含 7 个整数值的数组进行排序的递归归并排序算法。以下是人类模拟归并排序（自顶向下）的步骤：

完整视频教程可以参考油管博主[]Coding with John](https://www.youtube.com/@CodingWithJohn)的Merge Sort Algorithm in Java - Full Tutorial with Source，思路很清晰。

Java代码实现

import java.util.Random;

// Merge Sort Algorithm in Java - Full Tutorial with Source
// https://www.youtube.com/watch?v=bOk35XmHPKs

// Merge排序算法
public class MergeSortExample {
    public static void main(String[] args) {
        Random random = new Random();
        int[] numbers = new int[10];
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = random.nextInt(100);
        }
        System.out.println("Before Sort: ");
        printArray(numbers);

        mergeSort(numbers);

        System.out.println("\nAfter Quick Sort: ");
        printArray(numbers);
    }

    private static void mergeSort(int[] inputArray) {
        int inputLength = inputArray.length;

        if (inputLength < 2) {
            return;
        }

        int midIndex = inputLength / 2;
        int[] leftHalf = new int[midIndex];
        int[] rightHalf = new int[inputLength - midIndex];

        for (int i = 0; i < midIndex; i++) {
            leftHalf[i] = inputArray[i];
        }

        // System.arraycopy(inputArray, 0, leftHalf, 0, midIndex);

        for (int i = midIndex; i < inputLength; i++) {
            rightHalf[i - midIndex] = inputArray[i];
        }

//        if (inputLength - midIndex >= 0)
//            System.arraycopy(inputArray, midIndex, rightHalf, 0, inputLength - midIndex);

        mergeSort(leftHalf);
        mergeSort(rightHalf);

        merge(inputArray, leftHalf, rightHalf);
    }

    private static void merge(int[] inputArray, int[] leftHalf, int[] rightHalf) {
        int leftSize = leftHalf.length;
        int rightSize = rightHalf.length;

        int i = 0, j = 0, k = 0;
        while (i < leftSize && j < rightSize) {
            if (leftHalf[i] <= rightHalf[j]) {
                inputArray[k] = leftHalf[i];
                i++;
            } else {
                inputArray[k] = rightHalf[j];
                j++;
            }
            k++;
        }

        // 遍历左侧数组，将剩余元素添加到inputArray中
        while (i < leftSize) {
            inputArray[k] = leftHalf[i];
            i++;
            k++;
        }

        // 遍历右侧数组，将剩余元素添加到inputArray中
        while (j < rightSize) {
            inputArray[k] = rightHalf[j];
            j++;
            k++;
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + "\t");
        }
        System.out.println();
    }
}

可能的代码输入如下：

Before Sort: 
18	55	12	78	77	87	65	42	0	5	

After Quick Sort: 
0	5	12	18	42	55	65	77	78	87	

参考资料

• Merge sort-维基百科
• Merge Sort Algorithm in Java - Full Tutorial with Source
• Merge Sort-geeksforgeeks
• Merge sort
• Learn Merge Sort in 13 minutes 🔪