JAVA的归并排序怎么写
时间: 2023-03-10 10:54:38 浏览: 91
归并排序是一种分治算法,它的思想是将一个大的数组分成两个或多个小的数组,分别对这些小的数组进行排序,再将排序后的结果合并成一个大的有序数组。下面是 Java 实现的归并排序的代码:
```
public static void mergeSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
mergeSort(array, 0, array.length - 1);
}
private static void mergeSort(int[] array, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(array, l, mid);
mergeSort(array, mid + 1, r);
merge(array, l, mid, r);
}
private static void merge(int[] array, int l, int mid, int r) {
int[] temp = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = mid + 1;
while (p1 <= mid && p2 <= r) {
temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
while (p1 <= mid) {
temp[i++] = array[p1++];
}
while (p2 <= r) {
temp[i++] = array[p2++];
}
for (i = 0; i < temp.length; i++) {
array[l + i] = temp[i];
}
}
```
上面的代码是将整个数组分治递归排序的过程,最后调用 `merge` 函数将排好序的两个子数组合并为一个有序数组。