介绍
归并排序(Merge Sort)是一种高效且稳定的排序算法,它采用分治法(Divide and Conquer Technique)对数组进行排序。在本实验中,你将学习如何使用递归方法在 Java 中实现归并排序。
归并排序(Merge Sort)是一种高效且稳定的排序算法,它采用分治法(Divide and Conquer Technique)对数组进行排序。在本实验中,你将学习如何使用递归方法在 Java 中实现归并排序。
创建一个名为 mergeSort()
的公共静态方法,该方法接受三个整数参数:int arrToSort[]
、startIdx
和 endIdx
。你需要检查数组长度是否小于 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[]
、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;
}
}
让我们通过编写代码对输入数组进行排序来测试 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 中的归并排序实验。