归并排序

import java.util.Arrays; public class MergeSort { public static void mergeSort(int[] arrays, int left, int right) { // 如果数组还可以拆分 if (left < right) { //数组的中间位置 int middle = (left + right) / 2; //拆分左边数组 mergeSort(arrays, left, middle); //拆分右边数组 mergeSort(arrays, middle + 1, right); //合并 merge(arrays, left, middle, right); } } /** * 合并数组 */ public static void merge(int[] arr, int left, int middle, int right) { //申请合并空间 大小为两个已经排序序列之和 int[] temp = new int[right - left + 1]; //i 和 j为两个已经排好序的数组的起始位置 int i = left; int j = middle + 1; int k = 0; //排序 while (i <= middle && j <= right) { //将比较小的数组放入合并空间 if (arr[i] < arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } //将左边剩余元素写入合并空间 while (i <= middle) { temp[k++] = arr[i++]; } //将右边剩余的元素写入合并空间 while (j <= right) { temp[k++] = arr[j++]; } //将排序后的数组写回原来的数组 for (int l = 0; l < temp.length; l++) { arr[l + left] = temp[l]; } } public static void main(String[] args) { int[] ints = {5, 3, 4, 1, 2}; mergeSort(ints,0,ints.length-1); System.out.println(Arrays.toString(ints)); } }