java 实现 归并排序
时间: 2023-11-12 07:56:09 浏览: 54
归并排序是一种经典的分治算法,它将待排序的数组不断地二分,直到无法再分,然后对左右两个数组进行合并,最终得到一个有序的数组。Java 实现归并排序可以参考如下代码:
```
public class MergeSort {
public static void mergeSort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
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++];
}
System.arraycopy(temp, 0, arr, left, temp.length);
}
}
```