有序數(shù)組歸并

如果有兩個有序的數(shù)組將其合并成一個有序的數(shù)組，其時間復雜度為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;
} 

如果一個數(shù)組本身分成兩段有序的列表，那么上面的歸并如下流程：

   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)?？偣?code>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);
    }