归并排序：JAVA
主函数 main
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("Given Array");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.println("\nSorted array");
printArray(arr);
}
这个程序展示了如何使用Java实现归并排序，并且通过示例数组进行了测试。你可以根据需要修改输入数组或添加更多的功能。
- 功能: 程序的入口点，用于初始化一个数组并调用归并排序算法对其进行排序。
- 步骤:
- 定义一个整数数组
arr。 - 打印原始数组。
- 创建
MergeSort类的实例ob。 - 调用
ob的sort方法对数组进行排序。 - 归并排序函数
-
sort打印排序后的数组。 -
void sort(int arr[], int l, int r) { if (l < r) { // 找到中间点 int m = (l + r) / 2; // 对左半部分进行排序 sort(arr, l, m); // 对右半部分进行排序 sort(arr, m + 1, r); // 合并两个已排序的部分 merge(arr, l, m, r); } } - 功能: 递归地将数组分成两半，分别对每一半进行排序，然后合并这两部分。
- 参数:
arr: 要排序的数组。l: 当前子数组的起始索引。r: 当前子数组的结束索引。
- 步骤:
- 如果
l小于r，则继续分割数组。 - 计算中间点
m。 - 递归地对左半部分（从
l到m）进行排序。 - 递归地对右半部分（从
m+1到r）进行排序。 - 调用
merge方法合并两个已排序的部分。 -
合并函数
merge -
void merge(int arr[], int l, int m, int r) { // 找出左右子数组的大小 int n1 = m - l + 1; int n2 = r - m; // 创建临时数组 int L[] = new int[n1]; int R[] = new int[n2]; // 复制数据到临时数组中 for (int i = 0; i < n1; ++i) L[i] = arr[l + i]; for (int j = 0; j < n2; ++j) R[j] = arr[m + 1 + j]; // 合并临时数组 int i = 0, j = 0; int k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // 复制剩余的元素（如果有的话） while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } - 功能: 合并两个已排序的子数组。
- 参数:
arr: 要合并的数组。l: 左子数组的起始索引。m: 中间索引，分隔左右子数组。r: 右子数组的结束索引。
- 步骤:
- 计算左右子数组的大小
n1和n2。 - 创建两个临时数组
L和R，分别存储左右子数组的数据。 - 将原数组中的数据复制到临时数组
L和R。 - 使用双指针法合并两个临时数组，将较小的元素放入原数组中。
- 如果其中一个临时数组还有剩余元素，将其全部复制到原数组中。
-
打印数组函数
printArray -
static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } - 功能: 打印数组的内容。
- 参数:
arr，要打印的数组。 - 步骤:
- 获取数组的长度
n。 - 遍历数组，逐个打印每个元素，并在元素之间添加空格。
- 打印完所有元素后换行。
-
public class MergeSort { // 主函数，用于调用归并排序 public static void main(String[] args) { int[] arr = {12, 11, 13, 5, 6, 7}; System.out.println("Given Array"); printArray(arr); MergeSort ob = new MergeSort(); ob.sort(arr, 0, arr.length - 1); System.out.println("\nSorted array"); printArray(arr); } // 归并排序函数 void sort(int arr[], int l, int r) { if (l < r) { // 找到中间点 int m = (l + r) / 2; // 对左半部分进行排序 sort(arr, l, m); // 对右半部分进行排序 sort(arr, m + 1, r); // 合并两个已排序的部分 merge(arr, l, m, r); } } // 合并函数 void merge(int arr[], int l, int m, int r) { // 找出左右子数组的大小 int n1 = m - l + 1; int n2 = r - m; // 创建临时数组 int L[] = new int[n1]; int R[] = new int[n2]; // 复制数据到临时数组中 for (int i = 0; i < n1; ++i) L[i] = arr[l + i]; for (int j = 0; j < n2; ++j) R[j] = arr[m + 1 + j]; // 合并临时数组 int i = 0, j = 0; int k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // 复制剩余的元素（如果有的话） while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } // 打印数组的函数 static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } }代码解释：
main方法：初始化一个数组并调用sort方法对其进行排序，然后打印排序后的数组。sort方法：这是归并排序的核心递归方法。它首先检查数组是否至少有两个元素（即l < r），然后找到中间点m，递归地对左半部分和右半部分进行排序，最后调用merge方法将它们合并。merge方法：这个方法负责将两个已经排序的子数组合并成一个有序的数组。它使用两个临时数组L和R来存储左右子数组的数据，然后通过比较这两个临时数组中的元素，将较小的元素放入原数组中。printArray方法：这是一个辅助方法，用于打印数组的内容。