一昨凡、歸并排序

歸并排序的思路

歸并排序是典型的分治算法铐然，把一個(gè)數(shù)組的排序蔬崩，分為兩個(gè)子序列的排序，然后將兩個(gè)有序序列合并搀暑。以上就是整個(gè)算法的核心沥阳。整個(gè)過(guò)程如下圖所示（圖侵刪）：

歸并排序圖解

具體實(shí)現(xiàn)如下：

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

  public static void mergeSort(int[] arr, int l, int r) {
    if (l == r) {
      return;
    }
    // int mid = (l + r) / 2;
    // 等同于以上寫法，這樣的好處是防止溢出
    int mid = l + ((r - l) >> 1);
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
  }

  /// 合并兩個(gè)有序數(shù)組為新的有序數(shù)組
  public static void merge(int[] arr, int l, int m, int r) {
    int[] help = new int[r - l + 1];
    int i = 0;
    int p1 = l;
    int p2 = m + 1;
    // 逐一判斷左指針指向的數(shù)和右指針指向的數(shù)
    // 小的加入到數(shù)組中
    while (p1 <= m && p2 <= r) {
      help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    // 將剩余的數(shù)加入到數(shù)組中
    while (p1 <= m) {
      help[i++] = arr[p1++];
    }
    while (p2 <= r) {
      help[i++] = arr[p2++];
    }
    // 將臨時(shí)數(shù)組中的內(nèi)容拷貝回原數(shù)組中
    // （原left-right范圍的內(nèi)容被復(fù)制回原數(shù)組）
    for(i = 0; i < help.length; i++) {
      arr[l + i] = help[i];
    }
  }

二自点、歸并排序的延伸算法

1桐罕、小和問(wèn)題

題目描述如下：

在一個(gè)數(shù)組中，每一個(gè)數(shù)左邊比當(dāng)前數(shù)小的數(shù)累加起來(lái)桂敛，叫做這個(gè)數(shù)組的小和功炮。
求一個(gè)數(shù)組的小和。
例子:
[1,3,4,2,5] 
1左邊比1小的數(shù)术唬，沒有; 
3左邊比3小的數(shù)薪伏，1; 
4左邊比4小的數(shù)，1粗仓、3; 
2左邊比2小的數(shù)嫁怀，1; 
5左邊比5小的數(shù)，1借浊、3塘淑、4、2; 
所以小和為1+1+3+1+1+3+4+2=16

解題思路

把問(wèn)題轉(zhuǎn)化為在有序數(shù)組下蚂斤，對(duì)于下標(biāo)為i的數(shù)存捺，找出比i大的個(gè)數(shù)后，相乘再相加橡淆。因此召噩，我們需要進(jìn)行歸并排序，然后根據(jù)有序數(shù)組的特性逸爵，分布榨出小和

代碼實(shí)現(xiàn)

  public static int smallSum(int[] arr) {
    if (arr == null || arr.length < 2) {
      return 0;
    }
    return mergeSort(arr, 0, arr.length - 1);
  }
    
  public static int mergeSort(int[] arr, int l, int r) {
    if (l == r) {
      return 0;
    }
    // int mid = (l + r) / 2;
    // 等同于以上寫法具滴，這樣的好處是防止溢出
    int mid = l + ((r - l) >> 1);
    return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
  }
    
  /// 合并兩個(gè)有序數(shù)組為新的有序數(shù)組
  public static int merge(int[] arr, int l, int m, int r) {
    int[] help = new int[r - l + 1];
    int i = 0;
    int p1 = l;
    int p2 = m + 1;
    int res = 0;
    // 逐一判斷左指針指向的數(shù)和右指針指向的數(shù)
    // 小的加入到數(shù)組中
    while (p1 <= m && p2 <= r) {
      // 這里是歸并排序算法的基礎(chǔ)上添加的代碼
      res += arr[p1] < arr[p2] ? arr[p1] * (r - p2 + 1) : 0;
      help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    // 將剩余的數(shù)加入到數(shù)組中
    while (p1 <= m) {
      help[i++] = arr[p1++];
    }
    while (p2 <= r) {
      help[i++] = arr[p2++];
    }
    // 將臨時(shí)數(shù)組中的內(nèi)容拷貝回原數(shù)組中
    // （原left-right范圍的內(nèi)容被復(fù)制回原數(shù)組）
    for(i = 0; i < help.length; i++) {
      arr[l + i] = help[i];
    }
    return res;
  }

可以發(fā)現(xiàn)，相比歸并排序算法师倔，我們只在merge的過(guò)程中构韵，進(jìn)行了小和的計(jì)算。因此求出了每一個(gè)子序列的小和，全部子序列的小和相加即為整個(gè)序列的小和疲恢。

2凶朗、逆序?qū)?/h2>

在一個(gè)數(shù)組中，左邊的數(shù)如果比右邊的數(shù)大显拳，則折兩個(gè)數(shù)構(gòu)成一個(gè)逆序?qū)ε锓撸?qǐng)打印所有逆序?qū)Α?br> 例如：1, 5, 6, 3, 2的逆序?qū)?3,2), (5,2), (6,2), (5,3), (6,3)

算法思路

跟上一道題一樣，在merge的基礎(chǔ)上進(jìn)行拓展杂数。假設(shè)在一次merge的過(guò)程中宛畦，左序列的p1大于右序列的p2，那么揍移，根據(jù)子序列有序的特性次和，我們可以知道p1~mid的數(shù)，均大于p2那伐，因此可以組成mid - p1 + 1個(gè)逆序?qū)μなＲ虼苏页雒總€(gè)子merge過(guò)程的逆序?qū)Γ喜⒑蠛毖纯色@得所有的逆序?qū)?/p>

實(shí)現(xiàn)代碼

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

  public static int mergeSort(int[] arr, int l, int r) {
    if (l == r) {
      return 0;
    }
    int mid = (l + r) / 2;
    return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
  }

  public static int merge(int[] arr, int l, int m, int r) {
    int p1 = l;
    int p2 = m + 1;
    int[] help = new int[r - l + 1];
    int i = 0;
    int count = 0;

    while (p1 <= m && p2 <= r) {
      if (arr[p1] <= arr[p2]) {
        help[i++] = arr[p1++];
      }else {
        // 左 > 右畅形，說(shuō)明以p1為界限，p1~m之間的數(shù)據(jù)都大于右
        // 因此可推出逆序數(shù)的公式為 m - p1 + 1
        for(int k = p1; k <= m; k++) {
          System.out.print("(" + arr[k] + "," + arr[p2] + "), ");
        }
        count += m - p1 + 1;
        help[i++] = arr[p2++];
      }
    }
    while (p1 <= m) {
      help[i++] = arr[p1++];
    }
    while (p2 <= r) {
      help[i++] = arr[p2++];
    }
    // 拷貝
    for(i = 0; i < help.length; i++) {
      arr[l + i] = help[i];
    }
    return count;
  }