归并排序java实现

问题

使用归并排序如下数组 [32, 12, 43, 5, 3, 8],使得排序后的结果为：
[3, 5, 8, 12, 32, 43]

思路

解题需要以下两个知识：

1、归并排序的核心思想是分治思想，就是把需要排序的规模分到最小，本题中是要分到什么程度呢，也就是说分到每个数组里面只有一个元素，一个元素也就不用排了，就是这个元素本身

2、合并 两个有序的数组合并成一个有序的数组，这也就是这个归并排序名称的由来，具体归并的操作如下两个有序数组 a1=[1,3,5]和a2=[2,4,6] 合并之后是33=[1,2,3,4,5,6]。这里面主要用到两个指针，一个指向A1的开头p1，一个指向A2的开头p2，和一个空数组A3。然后比较a1[p1]和a2[p2]的大小，把小的放入到a3中，然后小的指针继续往下走，直到其中的一个数组的元素都走完，然后把另外一个数组的元素剩余的部分全部放入到a3结尾处。图例如下：

编码

 /**
   * 归并排序
   * @param a 待排序的数组
   */
  public void mergeSort(int[] a) {
    int[] temp = new int[a.length];
    mergeSortSub(a, temp, 0, a.length - 1);
  }

  /**
   * 需要用分治的代码,其中left<right是跳出循环的条件。
   * 分治之后调用merge函数对数组进行合并
   * @param a 待排序的数组
   * @param temp 临时用来存放数组的数组
   * @param left 分治以后的数组的左边界
   * @param right 分治之后数组的右边界
   */
  public void mergeSortSub(int[] a, int[] temp, int left, int right) {
    if (left < right) {
      int center = (left + right) / 2;
      mergeSortSub(a, temp, left, center);
      mergeSortSub(a, temp, center + 1, right);
      merge(a, temp, left, center + 1, right);
    }
  }


  /**
   * 一个数组从中间分为两个有序数组，合并这两个有序数组
   *
   * @param a        待排序和合并的数组
   * @param temp     合并和排序的结果
   * @param leftPos  左边有序数组起点
   * @param rightPos 右边有序数组的起点
   * @param rightEnd 右边的终点
   */
  public void merge(int[] a, int[] temp, int leftPos, int rightPos, int rightEnd) {

    int leftEnd = rightPos - 1;
    int tempPos = leftPos;
    int numElements = rightEnd - leftPos + 1;

    while (leftPos <= leftEnd && rightPos <= rightEnd) {
      int leftValue = a[leftPos];
      int rightValue = a[rightPos];
      if (leftValue > rightValue) {
        temp[tempPos] = rightValue;
        rightPos++;
      } else {
        temp[tempPos] = leftValue;
        leftPos++;
      }
      tempPos++;
    }
    while (leftPos <= leftEnd) {
      temp[tempPos] = a[leftPos];
      leftPos++;
      tempPos++;
    }
    while (rightPos <= rightEnd) {
      temp[tempPos] = a[rightPos];
      rightPos++;
      tempPos++;
    }
    for (int i = 0; i < numElements; i++, rightEnd--) {
      a[rightEnd] = temp[rightEnd];
    }
  }

//测试代码
 @Test
  public void test_mergeSort() {
  	int[] array = new int[]{32, 12, 43, 5, 3, 8};
    int[] after = new int[]{3, 5, 8, 12, 32, 43};
    mergeSort(array);
    Assert.assertArrayEquals(after, array);
  }

其中代码的执行流程如下图：

时间复杂度

O(NlogN)

以上就是java实现归并排序的全过程。最后再强调一遍，归并排序的两个关键点 分治和合并有序数组