请给出归并排序java版代码带注释和解释,最后输出结果
时间: 2023-07-07 18:12:10 浏览: 41
以下是归并排序的Java版代码,带有注释和解释,以及输出结果:
```java
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr = { 5, 3, 7, 6, 2, 1, 4 };
System.out.println("原始数组:" + Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1);
System.out.println("排序后数组:" + Arrays.toString(arr));
}
/**
* 归并排序
*
* @param arr 待排序数组
* @param left 左边界
* @param right 右边界
*/
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2; // 计算中间位置
mergeSort(arr, left, mid); // 对左半部分进行归并排序
mergeSort(arr, mid + 1, right); // 对右半部分进行归并排序
merge(arr, left, mid, right); // 合并左右两部分
}
}
/**
* 合并左右两部分
*
* @param arr 待合并数组
* @param left 左边界
* @param mid 中间位置
* @param right 右边界
*/
public static void merge(int[] arr, int left, int mid, int right) {
int[] tmp = new int[arr.length]; // 用于存储归并后的临时数组
int i = left; // 左半部分起始位置
int j = mid + 1; // 右半部分起始位置
int k = left; // 临时数组起始位置
while (i <= mid && j <= right) {
// 如果左半部分当前元素小于右半部分当前元素,就将左半部分当前元素放入临时数组中
// 否则,就将右半部分当前元素放入临时数组中
if (arr[i] < arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
// 将左半部分剩余元素依次放入临时数组中
while (i <= mid) {
tmp[k++] = arr[i++];
}
// 将右半部分剩余元素依次放入临时数组中
while (j <= right) {
tmp[k++] = arr[j++];
}
// 将临时数组中的元素复制回原数组中
for (int p = left; p <= right; p++) {
arr[p] = tmp[p];
}
}
}
```
这段代码首先定义了一个数组 `arr`,然后调用 `mergeSort` 函数对数组进行归并排序,最后输出排序后的数组。
`mergeSort` 函数是归并排序的主要实现,它采用递归的方式将数组分成左右两部分,分别进行归并排序,然后将左右两部分合并成一个有序数组。具体实现时,如果左边界小于右边界,就计算出中间位置 `mid`,然后对左半部分和右半部分分别进行归并排序,最后将左右两部分合并成一个有序数组。
`merge` 函数是将左右两部分合并成一个有序数组的实现,它先创建一个临时数组 `tmp`,然后将左右两部分中较小的元素放入临时数组中,直到某一部分的元素已经全部放入临时数组中为止。最后将剩余元素依次放入临时数组中,并将临时数组中的元素复制回原数组中。
输出结果为:
```
原始数组:[5, 3, 7, 6, 2, 1, 4]
排序后数组:[1, 2, 3, 4, 5, 6, 7]
```