归并排序大家都会写了吧，那你知道什么场景或什么题能派上用场吗？当涉及到数组元素中，每个元素要和左边所有，或右边所有元素进行比较的时候，这种情况下可以用归并排序，在排序的过程中，把事儿干了。
不理解的话，看下这个图就清楚了，我们现在只看3的心路历程，在merge的过程中，3第一次和1merge比较，然后进行下一个范围的merge，下下个……，每个新的范围所有数都会和3比较，比较的过程中可以实现特有的逻辑，当范围不断扩大，直到数组末尾的时候，3所有右边的数就完成了和3的比较过程。
现在有这么个题，求一个int数组的小和，就可以用这个思路来解。
什么是小和，int[] arr = {1, 2, 3, 2}，小和就是每个元素拿出来，所有左边比它小的数求和，再进行累加，比如arr里1左边没数，sum1 = 0，第二个数sum2=1，下面sum3=1+2，sum4=1，小和=sum1+sum2+sum3+sum4 = 5
这个题的思路有个转变， {1,2,3,4}小和的值里面有几个1？右边比1大的数都会产生1，共有3个，有几个2呢，右边比2大的数会产生2，共有2个，小和计算可以用这个思路转化为每个数右边有几个比它大，那么就产生右边那么多个它。
为了简单起见，用非递归的实现，逻辑直接和就是上图，大部分代码和归并排序一致，只是merge方法里稍有变化。
package class03; /** * @Description 归并排序非递归，求小和 * @Package: class03 * @Author: Ray * @CreateTime: 2020/7/4 15:28 * @E-mail: 634302021@qq.com */ public class Test8 { public static int mergeSort(int[] arr) { if (arr == null || arr.length == 1) { //空或一个数直接返回0 return 0; } //初始跨度为1 int span = 1; int num = 0; while (span < arr.length) { //for循环里每2个span进行截取出left,mid,right,然后merge排序 for (int i = 0; i < arr.length; i += 2 * span) { int left = i; int mid = left + span - 1; //2个跨度进行归并，mid为1个跨度的位置 /*处理边界，当最后一个mid定位超出了长度，表示最后几个数凑不到一个span， 本次span长度=上次while里span2倍，故也凑不齐上次while循环里的2*span， 凑不齐上次循环2个span的几个数在上次while里一定归并排序好了， 所以可以直接break */ if (mid >= arr.length - 1) { break; } int right = left + 2 * span - 1; if (right >= arr.length - 1) { //处理边界，右边界超出长度则直接为最后一位 right = arr.length - 1; } num += merge(arr, left, mid, right); //每个范围归并排序，计算小和进行累加 } span = span * 2; //跨度翻倍，翻倍变为2，4，8，16……从而以log（N）次循环整个数组长度 } return num; } //对排完序的left ~ mid, mid+1 ~ right范围进行归并排序 public static int merge(int[] arr, int left, int mid, int right) { int[] tmp = new int[right - left + 1]; //临时数组 int l = left; //左指针初始位置 int m = mid + 1; //右指针初始位置 int i = 0; //tmp下标 int num = 0; //小和 while (l <= mid && m <= right) { //任意左或右指针到边界则退出 if (arr[l] < arr[m]) { //只有当左小右大，才进行求和 //因为是有序的，右边m开始每个数都比l大，就产生（right-m+1）个arr[l] num += (right - m + 1) * arr[l]; tmp[i] = arr[l]; l += 1; } else { tmp[i] = arr[m]; m += 1; } i += 1; } while (l <= mid) { //如果左指针先循环完，剩下的数补到tmp上 tmp[i] = arr[l]; l += 1; i += 1; } while (m <= right) { //如果右指针先循环完，剩下的数补到tmp上 tmp[i] = arr[m]; m += 1; i += 1; } for (int j = 0; j < tmp.length; j++) { //tmp还原到原数组 arr[left + j] = tmp[j]; } return num; } public static void main(String[] args) { int[] arr = {1,2,3,2}; System.out.println(mergeSort(arr)); } }
