归并排序（Java）

归并排序的思想：

先实现一个数组的中间位置“断裂”为两个子数组，利用索引实现，一直到每一个都被分开；
直到最后两个数据都被分开后，然后借助辅助数组实现排序与合并操作；
最后递归返回到最初的时候，便实现了整个递归排序

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列[2]。

归并排序

归并排序的代码实现：

public class MergeSort{
  // 单独列出此函数，而不是直接调用Sort是因为输入只有arr数组，同时为了更好递归而设置的
  public static void MergeSort(int[] arr){
    Divide(arr, 0, arr.length-1)  
  }

  private static void Divide(int[] arr, int left, int right){
    if(left >= right) return;
    int mid = (left + right)/2;
    // 左右部分依次断裂，减少交换数据的作用
    Divide(arr, right, mid);
    Divide(arr, mid+1, right);
    // 最后才比较大小归并数组
    MergeAndSort(arr, left, mid, right);
  }

  private static void MergeAndSort(int[] arr, int left, int mid, int right){
    int[] tmpArr = new int[a.lenght];
    int rightStartIndex = mid + 1;
    int tmpIndex = left;
    int copyIndex = left;

    // 比较左右两部分数组的大小，小的放入到tmpArr数组中
    while(left <= mid && rightStartIndex <= right){
      if(arr[left] < arr[rightStartIndex]) tmpArr[tmpIndex++] = arr[left++];
      else tmpArr[tmpIndex++] = arr[rightStartIndex++];
    }
    // 判断左边是否还有数据剩余，如果有则把数据拷贝到tmpArr数组右边，因为左边已经是排好序的，所以剩余的数据肯定是最大的
    while(left <= mid){
      tmpArr[tmpIndex++] = arr[left++];
    }
    // 判断右边是否还有数据剩余，如果有则把数据拷贝到tmpArr数组右边，因为右边已经是排好序的，所以剩余的数据肯定是最大的
    while(rightStartIndex <= right){
      tmpArr[tmpIndex++] = arr[rightStartIndex++];
    }
    // 把tmpArr数组排好序的数据依次拷贝到原数组中
    while(copyIndex <= right){
      arr[copyIndex] = tmpArr[copyIndex];
      copyIndex++;
    }
  }
}

时空复杂度

时间复杂度

分析：主要是考虑两个函数的时间花销，一、数组划分函数Divide()；二、有序数组归并函数MergeAndSort()；
①调用Divide()函数把原数组划分成两部分，那每一小部分排序好所花时间则为 T[n/2]。
②MergeAndSort()函数的时间复杂度为O(n)，有两个时间复杂度为O(n)的while，一个是把非排序的数据保存到辅助数组，一个是把辅助数组中的数据拷贝到原数组。所以，2O(n) = O(n)
③把两部分都合并起来，就是
T(n) = 2T(n) + O(n)

结果就是T(n) = O(n*lgn)

空间复杂度

归并的空间复杂度就是临时的辅助数组和递归时压入栈的数据所占用的空间：n + logn；所以空间复杂度为: O(n)

参考文献：

[1] MergeSort（归并排序）算法Java实现
[2] 排序算法（Java）——那些年面试常见的排序算法
[3] 排序算法之归并排序及其时间复杂度和空间复杂度
[4]八大排序算法总结与java实现

最后编辑于：2018.03.27 14:53:54