归并排序java代码注释
时间: 2024-04-20 18:21:27 浏览: 25
归并排序是一种经典的排序算法,它采用分治的思想,将待排序的数组不断地分割成小的子数组,然后再将这些子数组合并成一个有序的数组。下面是归并排序的Java代码注释:
```java
public class MergeSort {
// 归并排序入口函数
public static void mergeSort(int[] arr) {
int[] temp = new int[arr.length]; // 创建一个临时数组用于存储排序结果
mergeSort(arr, 0, arr.length - 1, temp); // 调用递归函数进行归并排序
}
// 递归函数,实现归并排序
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2; // 计算中间位置
mergeSort(arr, left, mid, temp); // 对左半部分进行归并排序
mergeSort(arr, mid + 1, right, temp); // 对右半部分进行归并排序
merge(arr, left, mid, right, temp); // 合并左右两部分
}
}
// 合并函数,将两个有序的子数组合并成一个有序的数组
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 左子数组的起始位置
int j = mid + 1; // 右子数组的起始位置
int k = 0; // 临时数组的起始位置
// 将左右两个子数组中较小的元素依次放入临时数组中
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 将剩余的元素依次放入临时数组中
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 将临时数组中的元素复制回原数组
for (int m = 0; m < k; m++) {
arr[left + m] = temp[m];
}
}
}
```