一、小和问题

1、题目形容：

在一个数组中，每一个数右边比以后数小的数累加起来，叫做这个数组的小和。求一个给定数组的小和。

2、例子：

数组为：[1,3,4,2,5]

1右边比1小的数：没有

3右边比3小的数：1

4右边比4小的数：1,3

2右边比2小的数：1

5右边比5小的数：1,3,4,2

所以小和为1+(1+3)+1+(1+3+4+2)=16

3、思路：

找每一个数左边比以后数大的个数，(个数 * 以后数) 的累加和就是后果。

这咋和归并排序分割上的呢，认真想想，在左组和右组merge的时候，会比拟数的大小，这时就能够在右组找到比左组以后数大的个数。

4、具体的参考代码：

/** * 小和问题：在一个数组中，每一个数右边比以后数小的数累加起来，叫做这个数组的小和。要求工夫复杂度O(N*logN)  * * @author Java和算法学习：周一 */public class SmallSum {    public static int smallSum(int[] arr) {        if (arr == null || arr.length < 2) {            return 0;        }        return process(arr, 0, arr.length - 1);    }    private static int process(int[] arr, int l, int r) {        if (l == r) {            return 0;        }        int mid = l + ((r - l) >> 1);        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);    }    private static int merge(int[] arr, int l, int mid, int r) {        int[] help = new int[r - l + 1];        int i = 0;        int pL = l;        int pR = mid + 1;        int res = 0;        while (pL <= mid && pR <= r) {            // 当左组的数小于右组的数时， 以后右组的个数*以后数 的累加和 即是小和的后果            // 认真和归并排序比拟，发现就多了此处的代码。惟一的区别是，            // 等于的时候拷贝右组的，因为要在右组中找出比左组大的个数，必定不能先拷贝左组的，不然咋找出个数            res += arr[pL] < arr[pR] ? (r - pR + 1) * arr[pL] : 0;            help[i++] = arr[pL] < arr[pR] ? arr[pL++] : arr[pR++];        }        while (pL <= mid) {            help[i++] = arr[pL++];        }        while (pR <= r) {            help[i++] = arr[pR++];        }        for (int j = 0; j < help.length; j++) {            arr[l + j] = help[j];        }        return res;    }    /**     * 对数器办法     */    public static int comparator(int[] arr) {        int res = 0;        for (int i = 1; i < arr.length; i++) {            for (int j = 0; j < i; j++) {                res += arr[j] < arr[i] ? arr[j] : 0;            }        }        return res;    }    public static void main(String[] args) {        int maxSize = 100;        int maxValue = 100;        int testTimes = 100000;        boolean isSuccess = true;        for (int i = 0; i < testTimes; i++) {            int[] arr1 = generateArray(maxSize, maxValue);            int[] arr2 = copyArray(arr1);            if (smallSum(arr1) != comparator(arr2)) {                printArray(arr1);                printArray(arr2);                isSuccess = false;                break;            }        }        System.out.println(isSuccess ? "Nice" : "Error");    }    //------------------------------------------ TEST METHODS ----------------------------------------------    public static int[] generateArray(int maxSize, int maxValue) {        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];        for (int i = 0; i < arr.length; i++) {            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());        }        return arr;    }    public static int[] copyArray(int[] arr) {        if (arr == null) {            return null;        }        int[] res = new int[arr.length];        for (int i = 0; i < arr.length; i++) {            res[i] = arr[i];        }        return res;    }    public static void printArray(int[] arr) {        if (arr == null) {            return;        }        for (int value : arr) {            System.out.print(value + " ");        }        System.out.println();    }}

二、逆序对问题

1、题目形容：

设有一个数组 [a1, a2, a3,... an]，对于数组中任意两个元素ai，aj，若i<j，ai>aj，则阐明ai和aj是一对逆序对。求一个给定数组的逆序对个数。

2、例子：

3 5 2 1 0 4 9

所有逆序对是：(3,2)，(3,1)，(3,0)，(5,2)，(5,1)，(5,0)，(5,4)，(2,1)，(2,0)，(1,0)。逆序对个数为10。

3、思路：

合并的时候，从右往左合并，(此时右组地位 - mid地位) 的累加和即是逆序对个数。

这又咋和归并排序分割上的呢，认真想想，在左组和右组merge的时候，会比拟数的大小，然而我要找到的是左边更小的，所以能够采纳从右往左合并的形式；同时在解决相等的时候，须要先拷贝右组的，这样能力精确找出右组小的个数。

4、具体的参考代码：

/** * 逆序对问题：设有一个数组 [a1, a2, a3,... an]，对于数组中任意两个元素ai，aj，若i<j 且 ai>aj，则阐明ai和aj是一对逆序对。 * 求一个给定数组的逆序对个数。 * * @author Java和算法学习：周一 */public class ReversePair {    public static int reversePairNum(int[] arr) {        if (arr == null || arr.length < 2) {            return 0;        }        return process(arr, 0, arr.length - 1);    }    private static int process(int[] arr, int l, int r) {        if (l == r) {            return 0;        }        int mid = l + ((r - l) >> 1);        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);    }    private static int merge(int[] arr, int l, int mid, int r) {        // 辅助数组        int[] help = new int[r - l + 1];        // 辅助下标，因为从右往左合并，所以下标为数组最大值        int i = help.length - 1;        // 同理，左组第一个数地位为mid        int pL = mid;        // 右组第一个数为最初一个        int pR = r;        // 逆序对个数        int num = 0;        while (pL >= l && pR >= (mid + 1)) {            // 找到右组第一个比左组小的数，则以后满足要求的逆序对个数为 (pR - (mid + 1) + 1) 即是 (pR - mid)            num += arr[pL] > arr[pR] ? (pR - mid) : 0;            // 从右往左拷贝，相等的拷贝右组的            help[i--] = arr[pL] > arr[pR] ? arr[pL--] : arr[pR--];        }        // 左组和右组有且仅有一个未拷贝完，所以以下两个循环只会执行其中一个        while (pL >= l) {            help[i--] = arr[pL--];        }        while (pR > mid) {            help[i--] = arr[pR--];        }        // 拷贝回原数组        for (int j = 0; j < help.length; j++) {            arr[l + j] = help[j];        }        return num;    }    /**     * 对数器用于测试     */    public static int comparator(int[] arr) {        int num = 0;        for (int i = 0; i < arr.length; i++) {            for (int j = i + 1; j < arr.length; j++) {                if (arr[j] < arr[i]) {                    num++;                }            }        }        return num;    }    public static void main(String[] args) {        int testTime = 1000000;        int maxSize = 100;        int maxValue = 100;        boolean isSuccess = true;        for (int i = 0; i < testTime; i++) {            int[] arr1 = generateRandomArray(maxSize, maxValue);            int[] arr2 = copyArray(arr1);            if (reversePairNum(arr1) != comparator(arr2)) {                printArray(arr1);                printArray(arr2);                isSuccess = false;                break;            }        }        System.out.println(isSuccess ? "Nice" : "Error");    }    //--------------------------------------- 辅助测试的办法 ---------------------------------------------    public static int[] generateRandomArray(int maxSize, int maxValue) {        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];        for (int i = 0; i < arr.length; i++) {            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());        }        return arr;    }    public static int[] copyArray(int[] arr) {        if (arr == null) {            return null;        }        int[] res = new int[arr.length];        for (int i = 0; i < arr.length; i++) {            res[i] = arr[i];        }        return res;    }    public static void printArray(int[] arr) {        if (arr == null) {            return;        }        for (int value : arr) {            System.out.print(value + " ");        }        System.out.println();    }}

OK，明天就临时先说利用归并排序解决小和和逆序对问题的题目。

有时候，各种排序算法把握它自身并不难，难的是你可能充沛了解它的过程和精华，更难的是在真正遇到理论题目的时候，可能想到用这种排序算法来解决它。所以，算法无捷径，唯有多练习，在有足够多的量，积攒质变，而后能力迎来量变，那时能力信手拈来，加油。