java 归并排序怎么写,并给出代码
时间: 2023-03-14 22:11:53 浏览: 85
归并排序是一种分治算法,它将一个数组分成两个子数组,然后递归地将子数组排序,最后将排序后的子数组合并到一起。以下是按照 Java 语言编写的归并排序代码:public class MergeSort {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 6, 4, 2};
mergeSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
} public static void mergeSort(int[] arr, int left, int right) {
if (left >= right)
return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
} public static void merge(int[] arr, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
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 m = 0; m < tmp.length; m++) {
arr[left + m] = tmp[m];
}
}
}