package org.rev.algorithm;/** * 归并排序，属于交换排序，时间复杂度为算法复杂度Ο(n log n)，比快排序慢，但稳定。 *  * 1. 将一个序列递归拆分成多个有序的子序列。 *  * 2. 递归合并这些子序列，成为完整的子序列。 *  */public class MergeSort {  public static void main(String[] args) {    int[] data = {39, 11, 38, 97, 86, 37, 12, 4, 51, 18};    // 归并排序    MergeSort ms = new MergeSort();    ms.sort(data);    System.out.println("排序之后：");    ms.printData(data);  }  public void sort(int[] data) {    if (data.length > 0) { // length是0，就不能减1了。      mergeSort(data, 0, data.length - 1);    }  }  public void mergeSort(int[] data, int left, int right) {    if (left < right) {      int middle = (left + right) / 2;      System.out.println("left is:" + left + ", right is:" + right + ",  middle is:" + middle          + ",  data[" + middle + "]=" + data[middle]);      mergeSort(data, left, middle); // 对左边进行递归      mergeSort(data, middle + 1, right); // 对右边进行递归      merge(data, left, middle, right); // 归并      printData(data);    }  }  /**   * 归并两个数组，归并前两个数组是有序的，归并后的数组也是有序的。   *    * @param data 数组对象   * @param left 左数组第一个元素的索引   * @param middle 左数组的最后一个元素的索引，middle+1是右数组第一个元素的索引   * @param right 右数组最后一个元素的索引   */  private void merge(int[] data, int left, int middle, int right) {    // 临时数组    int[] tmpArr = new int[data.length];    // 右边的第一个元素的索引    int mid = middle + 1;    // tmp 临时变量，缓存左数组第一个元素的索引    int tmp = left;    // third 记录临时数组的索引    int third = left;    while (left <= middle && mid <= right) {      // 从两个数组中选取较小的数放入临时数组      if (data[left] <= data[mid]) {        tmpArr[third++] = data[left++];      } else {        tmpArr[third++] = data[mid++];      }    }    // 将剩余的部分放入临时数组    while (left <= middle) {      tmpArr[third++] = data[left++];    }    while (mid <= right) {      tmpArr[third++] = data[mid++];    }    // 将临时数组复制回原数组    while (tmp <= right) {      data[tmp] = tmpArr[tmp++];    }  }  /*   * 打印输出数组中的数据   */  private void printData(int[] data) {    for (int i = 0; i < data.length; i++) {      System.out.print(data[i] + "\t");    }    System.out.println();  }}