归并排序

有序数组归并

如果有两个有序的数组将其合并成一个有序的数组，其时间复杂度为O(n)

static int[] merge(int a[], int b[]) {
    int aLen = a.length;
    int bLen = b.length;
    int result[] = new int[aLen + bLen];
    int i = 0, j = 0, k = 0;
    while(i < aLen && j < bLen) {
        if(a[i] < b[j]) {
            result[k++]  = a[i++];
        } else {
            result[k++]  = b[j++];
        }
    }
    while(i < aLen) {
        result[k++]  = a[i++];
    }
    while(j < bLen) {
        result[k++]  = b[j++];
    }
    return result;
} 

如果一个数组本身分成两段有序的列表，那么上面的归并如下流程：

   static void merge(int a[], int l, int m, int r) {
         int help[] = new int[r - l + 1];
         int pl = l, pr = m + 1, i = 0;
         while (pl <= m && pr <= r) {
             if(a[pl] <= a[pr]) {
                 help[i++] = a[pl++];
             } else {
                 help[i++] = a[pr++];
             }
         }
         while (pl <= m) {
             help[i++] = a[pl++];
         }
        while (pr <= r) {
            help[i++] = a[pr++];
        }
        // copy from help
        for(i = 0, pl = l; i < help.length; i++) {
            a[pl++] = help[i];
        }
    }

归并排序

以{6,1,5,4,8,10,9,2}为例进行归并排序，如下图。实际上是一个递归回溯的问题。最底层满足两个子序列有序的条件归并后其上一层也满足两个子序列有序，类推直到最上层。每层的时间复杂度为O(n)。总共lgn层。所以总的时间复杂度为O(nlgn)

// 递归版本
static void mergeSort(int a[]) {
   if(a == null || a.length <= 1) return;
   help(a, 0, a.length - 1);
}
static void help(int a[], int l, int r) {
   if(l == r) return;
   int m = (l + r) / 2;
   // 分治
   help(a, l, m);
   help(a, m + 1, r);
   // 回溯
   merge(a, l, m, r);
}

// 非递归
static void mergeSort(int a[]) {
    if(a == null || a.length <= 1) return;
    // 每个归并子序列大小为range
    int range = 1, n = a.length;
    while(range < n) {
      for(int i = 0; i < n; i = i + range + range) {
         int l = i;
         int m = l + range - 1;
         int r = m + range;
         // 边界判断
         if(m >= n) continue;
         if(r >= n) r = n - 1;
         merge(a, l, m, r);
      }
      range = renge * 2;
    }
}

逆序对

题目：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

暴力方法：

  static int reversePairs(int a[]) {
        int result = 0;
        if(a == null || a.length <= 1) {
            return result;
        }
        int n = a.length;
        for(int i = 0; i < n - 1; i++) {
            for(int j = i + 1; j < n; j++) {
                if(a[j] < a[i]) {
                    result++;
                }
            }
        }
        return result;
    }

如果两个序列有序，在归并的过程中也可以求出逆序对。如1, 6跟2,3,8这两个序列归并过程中6比8小，此时8之前有两个元素2,3，所以整个序列6个逆序有2,3两个

   static int mergeReturnReversePairs(int a[], int l, int m, int r) {
        int help[] = new int[r - l + 1];
        int i = l, j = m + 1, k = 0, result = 0;
        while (i <= m && j <= r) {
            if(a[i] <= a[j]) {
                help[k++] = a[i++];
                result += j - m - 1;
            } else {
                help[k++] = a[j++];
            }
        }
        while (i <= m) {
            help[k++] = a[i++];
            result += j - m - 1;
        }
        while (j <= r) {
            help[k++] = a[j++];
        }
        for(i = l, k = 0; k < help.length; k++) {
            a[i++] = help[k];
        }
        return result;
    }

   static int help(int a[], int l, int r) {
        if(l == r) {
            return 0;
        }
        int m = (l + r) / 2;
        int r1 = help(a, l, m);
        int r2 = help(a, m + 1, r);
        int r3 = mergeReturnReversePairs(a, l, m, r);
        return r1 + r2 + r3;
    }

   static int reversePairs(int a[]) {
        if(a == null || a.length <= 1) return 0;
        return help(a, 0,  a.length - 1);
    }