算法学习笔记（五）归并排序及相关扩展

一. 归并排序

归并排序是一种稳定的排序，利用了递归思想，概括来说主要思路是：保证左半边有序；保证右半边有序；让整体有序。具体步骤为：

1. 将整个序列分为左右两个长度相同的子序列；
2. 两个子序列分别排序；
3. 合并两个子序列：创建一个与原序列等长的辅助数组；设置两个位置标记，分别指向两个子序列的起始位置；比较两个位置的元素，将较小值拷贝至辅助数组，并将标记移到下一个位置；重复上一步，直到一个序列中的位置标记即将越界，就将另一个序列中的剩余元素直接拷贝到辅助数组；将辅助数组的值拷回原数组。这个合并的过程可以看作小规模的外排序。
4. 递归执行上述步骤

此过程中T(N) = 2T(N/2) + O(N)，符合master公式的使用条件：T(N) = aT(N/b) + O(N^d)。此时log_ba = log₂2 = 1= d,因此时间复杂度为O(N*logN)。额外空间复杂度为O(N)。

Java

  public static void mergeSort(int[] arr) {
       if(arr==null || arr.length<2) {
           return;
       }
       mergeSort(arr, 0, arr.length-1);
   }
   
   public static void mergeSort(int[] arr, int left, int right) {
       if(right == left) {
           return;
       }
       int mid = left + ((right-left)>>1);
       mergeSort(arr, left, mid);
       mergeSort(arr, mid+1, right);
       merge(arr, left, mid, right);
   }
   
   public static void merge(int[] arr, int left, int mid, int right) {
       int[] arr2 = new int[right - left + 1];
       int i = 0;
       int p1 = left;
       int p2 = mid + 1;
       while(p1<=mid && p2<=right) {
           arr2[i++] = arr[p1]<arr[p2] ? arr[p1++] : arr[p2++];
       }
       while(p1 <= mid) {
           // p2右越界且p1未越过中间位置
           arr2[i++] = arr[p1++];
       }
       while(p2 <= right) {
           // p1到达中间位置，p2未到右边界
           arr2[i++] = arr[p2++];
       }
       for(i=0; i<arr2.length; i++) {
           arr[left+i] = arr2[i];
       }
   }

public static void main(String[] args) {
       int[] arr = {1,11,3,5,7,2,6,9,9};
       mergeSort(arr);
   }

JavaScript

var a =[1,11,3,5,7,2,6,9,9];
mergeSort(a);

function mergeSort(arr){
  if(arr===null || arr.length<2){
    return;
  }
  mergeSort(arr, 0, arr.length-1);
}

function mergeSort(arr, left, right){
  if(left === right){
    return;
  }
  var mid = left + ((right - left) >> 1);
  mergeSort(arr, left, mid);
  mergeSort(arr, mid+1, right);
  merge(arr, left, right);
}
function merge(arr, left, right){
  var arr2 = [];
  var mid = left + ((right - left) >> 1);
  var i = 0;
  var p1 = left;
  var p2 = mid + 1;
  while(p1<=mid && p2<=right){
    arr2[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
  }
  while(p1<=mid){
    arr2[i++] = arr[p1++];
  }
  while(p2<=right){
    arr2[i++] = arr[p2++];
  }
  for(i=0; i<arr.length; i++){
    arr[left + i] = arr2[i];
  }
}

二. 归并排序的扩展

先补充一些复杂度的优劣排序，常见的复杂度按照从优到劣的顺序排列，依次为:

最优 ——>

O(1)	O(logN)	O(logN^2)	O(N)	O(N*logN)	O(N^2)
O(N^3)	O(N^k) （k为常数）	O(2^n) （n步决定，每步都有2个决策）	O(3^n) （三叉树）	O(k^n) （k为常数 k叉树）	O(n!) （排列组合）

​ ——> 最劣

（1）小和问题

在一个数组中，每个数左边比它小的数相加，最后的结果称作这个数组的小和。在处理这个问题的过程中，可以先将原始的标准转化为更容易处理的等效标准。每个数被加了几次，就看它右边有多少个比它大的数。可以用归并排序的方法求小和，与归并排序的方式只有一点不同，那就是遇到相等值的情况，归并问题遇相等拷贝左部分或右部分的值都可以，而小和问题遇到相等时只能拷贝右侧的。因为要保证左侧的每个值被拷贝进来时都已经找到了比它大的。

假设数组 {1，3，4，2，5}

​ 1×4+3×2+4×1+2×1 = 16，这个数组的小和为16，和原始标准计算出的小和结果相同。

此问题也可以直接用遍历方式求解，但是时间复杂度为O(N^2)。如果采用上述方式，时间复杂度为O(N×logN).

具体的实现思路为：

1. 将数组划分为左右两部分；
2. 求左半部分的小和；
3. 求右半部分的小和；
4. 合并左右两部分，求左部分在右部分中的小和；
5. 将上三步的和相加，得到整个数组的小和；
6. 递归地执行上述步骤

每个数都不会错过右侧的所有范围，不会找漏；求小和只存在于跨组行为的时候，所以也不会找重。

Java

public static int smallSum(int[] arr) {
     if(arr==null || arr.length<2) {
         return 0;
     }else {
         return mergeSort(arr, 0, arr.length-1);
     }
 }
 
 public static int mergeSort(int[] arr, int left, int right) {
     int mid = left + ((right - left) >> 1);
     if(left == right) {
         return 0;
     }
     return mergeSort(arr, left, mid) + mergeSort(arr, mid+1, right) 
     + merge(arr, left, right);
 }
 
 public static int merge(int[] arr, int left, int right) {
     // 创建辅助数组
     int[] arr2 = new int[right - left + 1];
     // 辅助数组当前位置
     int i = 0;
     // 左半边数组的起始位置
     int p1 = left;
     // 数组的中间位置
     int mid = left + ((right - left) >> 1);
     // 右半边数组的起始位置
     int p2 = mid + 1;
     // 保存小和结果
     int res = 0;
     // 当左右都不越界时
     while(p1<=mid && p2<=right) {
         // 当左侧部分比右侧部分小时，产生小和
         res += arr[p1] < arr[p2] ? arr[p1]*(right - p2 + 1) : 0;
         // 把最小值放到辅助数组的下一个位置上
         arr2[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
     }
     // 当右半部分越界时
     while(p1 <= mid) {
         // 拷贝左半边的剩余数
         arr2[i++] = arr[p1++];
     }
     // 当左半部分越界时
     while(p2 <= right) {
         // 拷贝右半边的剩余数
         arr2[i++] = arr[p2++];
     }
     // 用辅助数组代替原数组
     for(i=0; i<arr2.length; i++) {
         arr[left+i] = arr2[i];
     }
     // 返回当前的小和
     return res;
 }
 
 public static void main(String[] args) {
     int[] arr = {1,3,4,2,5};
     System.out.println(smallSum(arr)); //16
 }

JavaScript

var a =[1,3,4,2,5];
console.log(smallSum(a)); //16

function smallSum(arr){
  if(arr===null || arr.length<2){
    return 0;
  }
  return mergeSort(arr, 0, arr.length-1);
}

function mergeSort(arr, left, right){
  if(left === right){
    return 0;
  }
  var mid = left + ((right-left) >> 1);
  return mergeSort(arr, left, mid) + mergeSort(arr, mid+1, right) + merge(arr, left, right);
}

function merge(arr, left, right){
  var mid = left + ((right-left) >> 1);
  var i = 0;
  var res = 0;
  var arr2 =[];
  var p1 = left;
  var p2 = mid + 1;
  while(p1<=mid && p2<=right){
    res += arr[p1] < arr[p2] ? arr[p1]*(right-p2+1) : 0;
    arr2[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
  }
  while(p1 <= mid){
    arr2[i++] = arr[p1++];
  }
  while(p2 <= right){
    arr2[i++] = arr[p2++];
  }
  for(i=0; i<arr2.length; i++){
    arr[left + i] = arr2[i];
  }
  return res;
}

（2）逆序对问题

在数组中，如果左边的数比右边的数大，那么这两个数就构成一个逆序对。比如数组{3,1,2,4,2,1}，其中存在的逆序对有：2,1; 3,2; 3,1; 2,4等等。要求打印出所有逆序对。此题目也可以直接用遍历的方法解出，但是时间复杂度为O(N^2)。同样可以利用归并排序的思路求解，与小和问题类似，都是merge的活用。将标准转化为右侧有多少个数比它小。

Java

// 用来记录逆序对的个数
private static int count = 0;

public static void reverse(int[] arr) {
    if(arr==null || arr.length<2) {
        return;
    }
    mergeSort(arr, 0, arr.length-1);
}

public static void mergeSort(int[] arr, int left, int right) {
    if(left == right) {
        return;
    }
    int mid = left + ((right - left) >> 1);
    // 打印左边存在的逆序对
    mergeSort(arr, left, mid);
    // 打印右边存在的逆序对
    mergeSort(arr, mid+1, right);
    // 打印左右两边合并后存在的逆序对
    merge(arr, left, right);
}

public static void merge(int[] arr, int left, int right) {
    int mid = left + ((right - left) >> 1);
    // 新的辅助数组
    int[] arr2 = new int[right - left + 1];
    // 新数组的起始位置
    int i = 0;
    // 左边的起始位置
    int p1 = left;
    // 右边的起始位置
    int p2 = mid + 1;
    while(p1<=mid && p2<=right) {
        // 当p1处的值大于p2处的值时，p1处的值也大于p2之后位置的值
        if(arr[p1] > arr[p2]) {
            // 打印包括p2及其后的逆序对
            for(int j=p2; j<=right; j++) {
                System.out.println(arr[p1] + " " + arr[j]);
            }
            count += (right - p2 + 1);
            arr2[i++] = arr[p1++];
        }else {
            arr2[i++] = arr[p2++];
        }
    }
    // 右侧到达边界时，左侧直接全部拷贝
    while(p1 <= mid) {
        arr2[i++] = arr[p1++];
    }
    // 左侧到达边界时，右侧直接全部拷贝
    while(p2 <= right) {
        arr2[i++] = arr[p2++];
    }
    for(i=0; i<arr2.length; i++) {
        arr[left + i] = arr2[i];
    }
}

public static void main(String[] args) {
    int[] arr = {3,1,4,5,2};
    reverse(arr);
    System.out.println("共有"+count+"个逆序对");
}

JavaScript

var a =[3,1,4,5,2];
var count = 0;
reverse(a);
console.log("共有"+count+"个逆序对");

function reverse(arr){
  if(arr===null || arr.length<2){
    return;
  }
  mergeSort(arr, 0, arr.length-1);
}

function mergeSort(arr, left, right){
  if(left === right){
    return;
  }
  var mid = left + ((right - left) >> 1);
  mergeSort(arr, left, mid);
  mergeSort(arr, mid+1, right);
  merge(arr, left, right);
}

function merge(arr, left, right){
  var arr2 = [];
  var i = 0;
  var p1 = left;
  var mid = left + ((right - left) >> 1);
  var p2 = mid + 1;
  while(p1<=mid && p2<=right){
    if(arr[p1] > arr[p2]){
      for(var j=p2; j<=right; j++){
        console.log(arr[p1] + " " + arr[p2]);
      }
      arr2[i++] = arr[p1++];
      count += (right - p2 + 1);
    }else{
      arr2[i++] = arr[p2++];
    }
  }
  while(p1 <= mid){
    arr2[i++] = arr[p1++];
  }
  while(p2 <= mid){
    arr2[i++] = arr[p2++];
  }
  for(i=0; i<arr2.length; i++){
    arr[left+i] = arr2[i];
  }
}