Java 中的递归归并排序实现

JavaJavaBeginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

介绍

归并排序(Merge Sort)是一种高效且稳定的排序算法,它采用分治法(Divide and Conquer Technique)对数组进行排序。在本实验中,你将学习如何使用递归方法在 Java 中实现归并排序。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL java(("`Java`")) -.-> java/BasicSyntaxGroup(["`Basic Syntax`"]) java(("`Java`")) -.-> java/DataStructuresGroup(["`Data Structures`"]) java(("`Java`")) -.-> java/ProgrammingTechniquesGroup(["`Programming Techniques`"]) java(("`Java`")) -.-> java/ConcurrentandNetworkProgrammingGroup(["`Concurrent and Network Programming`"]) java(("`Java`")) -.-> java/SystemandDataProcessingGroup(["`System and Data Processing`"]) java/BasicSyntaxGroup -.-> java/output("`Output`") java/DataStructuresGroup -.-> java/arrays("`Arrays`") java/DataStructuresGroup -.-> java/arrays_methods("`Arrays Methods`") java/DataStructuresGroup -.-> java/sorting("`Sorting`") java/ProgrammingTechniquesGroup -.-> java/recursion("`Recursion`") java/ConcurrentandNetworkProgrammingGroup -.-> java/working("`Working`") java/SystemandDataProcessingGroup -.-> java/string_methods("`String Methods`") subgraph Lab Skills java/output -.-> lab-117972{{"`Java 中的递归归并排序实现`"}} java/arrays -.-> lab-117972{{"`Java 中的递归归并排序实现`"}} java/arrays_methods -.-> lab-117972{{"`Java 中的递归归并排序实现`"}} java/sorting -.-> lab-117972{{"`Java 中的递归归并排序实现`"}} java/recursion -.-> lab-117972{{"`Java 中的递归归并排序实现`"}} java/working -.-> lab-117972{{"`Java 中的递归归并排序实现`"}} java/string_methods -.-> lab-117972{{"`Java 中的递归归并排序实现`"}} end

创建归并排序方法

创建一个名为 mergeSort() 的公共静态方法,该方法接受三个整数参数:int arrToSort[]startIdxendIdx。你需要检查数组长度是否小于 2,如果是,则直接返回。否则,计算数组的中间索引,并将数组拆分为左右两半。左右两半也需要递归地进行拆分。拆分完成后,你需要将它们合并以形成一个有序数组。

public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
    if (startIdx >= endIdx) {
        return;
    }

    int midIdx = startIdx + (endIdx - startIdx) / 2;
    mergeSort(arrToSort, startIdx, midIdx);
    mergeSort(arrToSort, midIdx + 1, endIdx);
    merge(arrToSort, startIdx, midIdx, endIdx);
}

创建合并方法

创建另一个名为 merge() 的公共静态方法,该方法接受四个参数:int arrToSort[]startIdxmidIdxendIdx。你需要初始化左数组和右数组。然后,通过比较每个数组的元素并将它们合并为一个数组来完成合并操作。

public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
    int[] leftArr = new int[midIdx - startIdx + 1];
    int[] rightArr = new int[endIdx - midIdx];

    for (int i = 0; i < leftArr.length; i++) {
        leftArr[i] = arrToSort[startIdx + i];
    }
    for (int i = 0; i < rightArr.length; i++) {
        rightArr[i] = arrToSort[midIdx + i + 1];
    }

    int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
    while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
        if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
            arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
            leftArrIdx += 1;
        } else {
            arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
            rightArrIdx += 1;
        }
        sortedArrIdx += 1;
    }

    while (leftArrIdx < leftArr.length) {
        arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
        leftArrIdx += 1;
        sortedArrIdx += 1;
    }

    while (rightArrIdx < rightArr.length) {
        arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
        rightArrIdx += 1;
        sortedArrIdx += 1;
    }
}

测试归并排序

让我们通过编写代码对输入数组进行排序来测试 mergeSort() 方法。创建一个主方法。然后,声明一个包含一些未排序值的整数数组。调用 mergeSort() 方法并将未排序的数组传递给它。最后,将排序后的数组打印到控制台。此步骤的代码块如下所示:

public static void main(String[] args) {
    int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
    mergeSort(arrToSort, 0, arrToSort.length - 1);
    System.out.println(Arrays.toString(arrToSort));
}

运行程序后,输出应为:[0, 1, 2, 4, 6, 8]

测试空数组

为测试空数组创建另一个测试用例。声明一个空的整数数组。调用 mergeSort() 方法并将空数组传递给它。最后,将排序后的数组打印到控制台。此步骤的代码块如下所示:

int[] emptyArr = {};
mergeSort(emptyArr, 0, emptyArr.length - 1);
System.out.println(Arrays.toString(emptyArr));

输出应与输入相同。

测试单元素数组

为测试单元素数组创建另一个测试用例。声明一个单元素的整数数组。调用 mergeSort() 方法并将单元素数组传递给它。最后,将排序后的数组打印到控制台。此步骤的代码块如下所示:

int[] singleElementArr = {7};
mergeSort(singleElementArr, 0, singleElementArr.length - 1);
System.out.println(Arrays.toString(singleElementArr));

输出应与输入相同。

测试包含负值的数组

为测试包含负整数的数组创建另一个测试用例。声明一个包含一些负整数的整数数组。调用 mergeSort() 方法并将该数组作为参数传递。最后,将排序后的数组打印到控制台。此步骤的代码块如下所示:

int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
System.out.println(Arrays.toString(arrWithNegatives));

运行程序后,输出应为:[-9, -7, -1, 0, 2, 6, 8]

测试非数值元素数组

为测试非数值元素数组创建另一个测试用例。声明一个字符串数组。调用 mergeSort() 方法并将该数组作为参数传递。最后,将排序后的数组打印到控制台。此步骤的代码块如下所示:

String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
mergeSort(strsToSort, 0, strsToSort.length - 1);
System.out.println(Arrays.toString(strsToSort));

运行程序后,输出应为:['Bob', 'Christine', 'David', 'Emily', 'John']

最终源代码

以下是归并排序(Merge Sort)的最终源代码:

import java.util.Arrays;

public class MergeSort {
   public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
       if (startIdx >= endIdx) {
           return;
       }

       int midIdx = startIdx + (endIdx - startIdx) / 2;
       mergeSort(arrToSort, startIdx, midIdx);
       mergeSort(arrToSort, midIdx + 1, endIdx);
       merge(arrToSort, startIdx, midIdx, endIdx);
   }

   public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
       int[] leftArr = new int[midIdx - startIdx + 1];
       int[] rightArr = new int[endIdx - midIdx];

       for (int i = 0; i < leftArr.length; i++) {
           leftArr[i] = arrToSort[startIdx + i];
       }

       for (int i = 0; i < rightArr.length; i++) {
           rightArr[i] = arrToSort[midIdx + i + 1];
       }

       int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
       while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
           if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
               arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
               leftArrIdx += 1;
           } else {
               arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
               rightArrIdx += 1;
           }
           sortedArrIdx += 1;
       }

       while (leftArrIdx < leftArr.length) {
           arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
           leftArrIdx += 1;
           sortedArrIdx += 1;
       }

       while (rightArrIdx < rightArr.length) {
           arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
           rightArrIdx += 1;
           sortedArrIdx += 1;
       }
   }

   public static void main(String[] args) {
       //创建一个未排序的整数数组
       int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
       //使用归并排序对整数数组进行排序
       mergeSort(arrToSort, 0, arrToSort.length - 1);
       //打印排序后的数组
       System.out.println(Arrays.toString(arrToSort));

       //创建一个空整数数组
       int[] emptyArr = {};
       //对空数组进行排序
       mergeSort(emptyArr, 0, emptyArr.length - 1);
       //打印排序后的数组
       System.out.println(Arrays.toString(emptyArr));

       //创建一个单元素数组
       int[] singleElementArr = {7};
       //对单元素数组进行排序
       mergeSort(singleElementArr, 0, singleElementArr.length - 1);
       //打印排序后的数组
       System.out.println(Arrays.toString(singleElementArr));

       //创建一个包含负数的整数数组
       int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
       //对包含负数的数组进行排序
       mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
       //打印排序后的数组
       System.out.println(Arrays.toString(arrWithNegatives));

       //创建一个字符串数组
       String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
       //对字符串数组进行排序
       mergeSort(strsToSort, 0, strsToSort.length - 1);
       //打印排序后的数组
       System.out.println(Arrays.toString(strsToSort));
   }
}

运行程序

使用终端编译并运行程序:

javac MergeSort.java && java MergeSort

总结

在本实验中,你学习了什么是归并排序(Merge Sort),它是如何工作的,以及如何在 Java 中实现它。你创建了两个公共静态方法 mergeSort()merge(),分别用于分割和合并输入数组。在实现之后,你在多种输入上进行了测试,讨论了时间复杂度和空间复杂度,并验证了其功能。恭喜!你已成功完成了 Java 中的归并排序实验。

您可能感兴趣的其他 Java 教程