实现代码
package com.wllarl.suanfa.sort; import java.util.Arrays; //归并排序 public class MergetSort { public static void main(String[] args) { int arr[] = {8,4,5,7,1,3,5,6,2}; int temp[] = new int[arr.length]; mergetSort(arr,0,arr.length-1,temp); System.out.println(Arrays.toString(arr)); } public static void mergetSort(int[] arr,int left,int right,int []temp){ if (left < right) { int mid = (left + right) / 2; //向左递归 mergetSort(arr,left,mid,temp); //向右递归 mergetSort(arr,mid+1,right,temp); //合并 merge(arr,left,mid,right,temp); } } /** * 归并排序的和方法 * @param arr 代表原数组 * @param left 左边索引 * @param mid 中间索引 * @param right 右边索引 * @param temp 临时数组 */ public static void merge(int[] arr,int left,int mid,int right,int[] temp){ int i = left; int j = mid + 1; int t = 0;//代表临时数组的下表 while (i <= mid && j <= right){ if (arr[i] <= arr[j]){ temp[t] = arr[i]; t += 1; i += 1; }else { temp[t] = arr[j]; t += 1; j += 1; } } while (i <= mid){ temp[t] = arr[i]; i += 1; t += 1; } while (j <= right){ temp[t] = arr[j]; j += 1; t += 1; } t = 0; int tempLift = left; while (tempLift <= right){ arr[tempLift] = temp[t]; tempLift += 1; t += 1; } } }实验结果 [1, 2, 3, 4, 5, 5, 6, 7, 8]
