写一段java 归并排序
时间: 2023-05-23 15:06:09 浏览: 50
以下是一段 Java 归并排序的代码:
```java
public class MergeSort {
public void mergeSort(int[] arr) {
int n = arr.length;
if (n < 2) {
return;
}
int mid = n / 2;
int[] left = new int[mid];
int[] right = new int[n - mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < n; i++) {
right[i - mid] = arr[i];
}
mergeSort(left);
mergeSort(right);
merge(left, right, arr);
}
public void merge(int[] left, int[] right, int[] arr) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
}
```
在上面的代码中,我们定义了一个 `MergeSort` 类,它包含两个方法,`mergeSort` 和 `merge`。`mergeSort` 方法递归地调用自身,将待排序的数组分成两半,分别对它们进行归并排序,最后再将两个有序的子数组合并起来。`merge` 方法用于将两个已排序的数组合并成一个有序的数组。这是通过比较数组中元素的大小来完成的。在每次比较中,我们将较小的元素放入新数组中,并递增已处理元素的计数器(`i` 和 `j`),直到有一个数组的所有元素都被处理完毕。然后我们将另一个数组中剩余的元素添加到新数组中。最终,我们将新数组中的元素复制回原始数组。