1、归并排序采用的是分治法的思想来解决的，跟快速排序一样，思路图如下： 大体思路就是：将一个数组等长的分割，一直分割，直到只剩单个元素，这个是递归的出口，然后又从底层一层一层的合并，每一层中，两个子数组，挑选最小的一个放进暂存的数组中，然后将暂存数组中的元素复制回原来的数组。完成计算。 2、代码实现如下：参考网友的，然后自己理解又重写了一次，记住，一定要先了解这个算法的思想，利用图来理解，然后才是编码实现
package com.paixu; import sun.nio.cs.UTF_32LE; import java.util.ArrayList; import java.util.Arrays; /** * 归并排序（合并排序：分治算法的思想） * 将一个数组一分为二（长度相等的子序列），然后继续分，直到只剩一个元素，然后在合并回去。 */ public class guiBingPaiXu { public static void main(String[] args) { int[] arr = new int[]{5,4,3,2,1,2,3,4,5}; int start = 0; int end = arr.length-1; mergSort(arr,start,end); System.out.println(Arrays.toString(arr)); } // 分 private static void mergSort(int[] arr, int start, int end) { if (start<end){ // 当分到只有一个元素的时候返回 // 这里特别注意 // 等长的分 int mid = (start+end)/2; mergSort(arr,start,mid); mergSort(arr,mid+1,end); // 合并 mergHebing(arr,start,mid,end); } } // 合并 private static void mergHebing(int[] arr, int start, int mid, int end) { int[] temp = new int[end-start+1]; // 这里特别注意 int leftIndex = start; int rightIndex = mid+1; int tempIndex = 0; while (leftIndex<=mid && rightIndex<=end){ // 将两个子数组比较，将小的存进去 if (arr[leftIndex]<arr[rightIndex]){ temp[tempIndex++] = arr[leftIndex++]; }else { temp[tempIndex++] = arr[rightIndex++]; } } // 将左边剩下的加入 while (leftIndex<=mid){ temp[tempIndex++] = arr[leftIndex++]; } // 将右边剩下的加入 while (rightIndex<=end){ temp[tempIndex++] = arr[rightIndex++]; } // 将暂存数组的元素复制回原数组 for (int i=0;i<temp.length;i++){ arr[i+start] = temp[i]; // 这里特别注意 } } }3、算法是稳定的
