小和问题

image.png
之所以能够使用归并排序进行解决，是因为归并排序在**merge**的时候，会进行两部分的比较，例如
image.png
每次merge都可以计算出在这次merge中形成的小和，最后相加即为答案

  1. public class xiaohe {
  2.     public static void main(String[] args) {
  3.         int[] array = new int[]{1,2,3};
  4.         System.out.println(mergeSort(array, 0, array.length - 1));
  6.     }
  7.     //给数组中left到right范围的子序列做归并排序
  8.     public static int mergeSort(int[] array,int left,int right) {
  9.         if (left == right) {
  10.             //说明这个子数组只有一个值了，一定是有序的,直接返回即可
  11.             return 0;
  12.         }
  13.         //递归，再分子数组
  14.         //先得到中间位置(mid = left + (right-left)/2)
  15.         int mid = left + ((right-left) >> 1);
  16.         return mergeSort(array,left,mid) +
  17.                 mergeSort(array,mid+1,right) +
  18.                 //左右子序列排好序了，现在把左右子序列做一个归并
  19.                 merge(array,left,mid+1,right);
  20.     }
  21.     //index1是左子序列的起始值
  22.     //index2是有右子序列的起始值
  23.     //right是右子序列的终点
  24.     public static int merge(int[] array,int index1,int index2,int right) {
  25.         //index1是左子序列的位置
  26.         //index2是右子序列的位置
  27.         int sum = 0 ;
  28.         int left = index1;
  29.         int[] tmp = new int[right-index1+1];
  30.         int record = index2;
  31.         int index = 0 ;
  32.         while (index1 < record && index2<=right) {
  33.             //如果左边比右边小,那左边这个数就要比右边这个数以及右边这个数还大的数小
  34.             sum += array[index] < array[index2] ? (right-index2+1) * array[index1] : 0;
  35.             tmp[index++] = array[index1]>=array[index2]? array[index2++]:array[index1++];
  36.         }
  37.         while (index1 < record) {
  38.             tmp[index++] = array[index1++];
  39.         }
  40.         while (index2 <= right) {
  41.             tmp[index++] = array[index2++];
  42.         }
  43.         for (int i=0;i<tmp.length;i++) {
  44.             array[left+i] = tmp[i];
  45.         }
  46.         return sum;
  47.     }
  48. }

逆序对问题

image.png
与小和问题类似，这个是求merge过程中，左侧子序列中的数比右侧子序列中的数更大的情况。

  1. public class nixudui {
  2.     public static void main(String[] args) {
  3.         int[] array = new int[]{3,2,1};
  4.         mergeSort(array, 0, array.length - 1);
  6.     }
  7.     //给数组中left到right范围的子序列做归并排序
  8.     public static void mergeSort(int[] array,int left,int right) {
  9.         if (left == right) {
  10.             //说明这个子数组只有一个值了，一定是有序的,直接返回即可
  11.             return ;
  12.         }
  13.         //递归，再分子数组
  14.         //先得到中间位置(mid = left + (right-left)/2)
  15.         int mid = left + ((right-left) >> 1);
  16.         mergeSort(array,left,mid);
  17.         mergeSort(array,mid+1,right);
  18.         //左右子序列排好序了，现在把左右子序列做一个归并
  19.         merge(array,left,mid+1,right);
  20.     }
  21.     //index1是左子序列的起始值
  22.     //index2是有右子序列的起始值
  23.     //right是右子序列的终点
  24.     public static void merge(int[] array,int index1,int index2,int right) {
  25.         //index1是左子序列的位置
  26.         //index2是右子序列的位置
  27.         int left = index1;
  28.         int[] tmp = new int[right-index1+1];
  29.         int record = index2;
  30.         int index = 0 ;
  31.         while (index1 < record && index2<=right) {
  32.             //如果左边比右边大,那左边这个数和左子序列中大于左边的这个数 会与 右边的数形成逆序对
  33.             if (array[index1] > array[index2]) {
  34.                 for (int i=index1;i<record;i++) {
  35.                     System.out.println("(" + array[i] + "," + array[index2] + ")");   
  36.                 }
  37.             }
  38.             tmp[index++] = array[index1]>=array[index2]? array[index2++]:array[index1++];
  39.         }
  40.         while (index1 < record) {
  41.             tmp[index++] = array[index1++];
  42.         }
  43.         while (index2 <= right) {
  44.             tmp[index++] = array[index2++];
  45.         }
  46.         for (int i=0;i<tmp.length;i++) {
  47.             array[left+i] = tmp[i];
  48.         }
  49.     }
  50. }