归并排序以及衍生小和、逆序对问题

package learn.note.algorithm.sort.three;

import java.util.Arrays;

/**
 * @author Wang WenLei
 * @date 2025/7/30 17:29
 * @since 1.0
 */
public class MergeSort {
    public static void main(String[] args) {
        int [] data = {5,4,3,2,1};
        mergeSort(data);
        Arrays.stream(data).forEach(System.out::print);

        // 对数器
        CompareMachineUtil.compare(MergeSort::mergeSort, null);
    }

    public static void mergeSort(int [] data) {
        mergeSort(data,0,data.length-1);
    }

    public static void mergeSort(int [] data,int low,int high){
        if (data == null || high - low < 1) {
            return;
        }
        int middle = low + ((high - low) >> 1);
        mergeSort(data,low,middle);
        mergeSort(data,middle + 1, high);
        // 合并
        merge(data,low,middle,high);
    }

    private static void merge(int[] data, int low, int middle, int high) {
        int[] tempArr = new int[high - low + 1];
        int i = 0;
        int p1 = low;
        int p2 = middle + 1;

        // 这里都需要等于，左边是从0开始到分界点。右边是从分界点+1开始到数组结束
        // 边界都是闭区间，所以需要等于
        while (p1 <= middle && p2 <= high) {
            if (data[p1] < data[p2]) {
                tempArr[i++] = data[p1++];
            } else {
                tempArr[i++] = data[p2++];
            }
        }
        while (p1 <= middle) {
            tempArr[i++] = data[p1++];
        }
        while (p2 <= high) {
            tempArr[i++] = data[p2++];
        }

        for (i = 0 ; i < tempArr.length ; i++) {
            data[low + i] = tempArr[i];
        }
    }
}

关于对数器请看：readme

归并排序衍生

必出

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例如：[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

package learn.note.algorithm.sort.three.mergeextension;

/**
 * @author Wang WenLei
 * @date 2025/8/4 13:42
 * @since 1.0
 */
public class LittleSum {
    public static void main(String[] args) {
        int [] data = new int[]{1,3,4,2,5};
        System.out.println(littleSum(data));
    }

    public static int littleSum(int [] data) {
        return mergeSort(data, 0 , data.length - 1);
    }

    public static int mergeSort(int [] data, int low, int high) {
        if (data == null || low == high) {
            return 0;
        }
        int middle = low + ((high - low) >> 1);
        return mergeSort(data,low,middle) + mergeSort(data,middle + 1,high) + merge(data,low,middle,high);
    }

    public static int merge(int [] data, int low, int middle, int high) {
        int[] tempArr = new int[high - low + 1];
        int res = 0;
        int i = 0;
        int p1 = low;
        int p2 = middle + 1;
        while (p1 <= middle && p2 <= high) {
//            简写
//            res += data[p1] < data[p2] ? (high - p2 + 1) * data[p1] : 0;
//            tempArr[i++] = data[p1] < data[p2] ? data[p1++] : data[p2++];
            if (data[p1] < data[p2]) {
                // 先累加再调整位置
                res += (high - p2 + 1) * data[p1];
                tempArr[i++] = data[p1++];
            } else {
                tempArr[i++] = data[p2++];
            }
        }
        while (p1 <= middle) {
            tempArr[i++] = data[p1++];
        }
        while (p2 <= high) {
            tempArr[i++] = data[p2++];
        }

        for (i = 0 ; i < tempArr.length ; i ++) {
            data[low + i] = tempArr[i];
        }
        return res;
    }
}

逆序对问题

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有的逆序对/请得到逆序对个数。

package learn.note.algorithm.sort.three.mergeextension;

/**
 * @author Wang WenLei
 * @date 2025/8/4 16:09
 * @since 1.0
 */
public class ReversePair {
    public static void main(String[] args) {
        int[] data = new int[] {1,3,5,2,4};
        System.out.println(reversePair(data));
    }

    public static int reversePair(int [] data) {
        return reversePair(data, 0, data.length - 1);
    }

    private static int reversePair(int[] data, int low, int high) {
        if (low == high) {
            return 0;
        }
        int mid = low + ((high - low) >> 1);
        return reversePair(data, low, mid) + reversePair(data, mid + 1, high) + merge(data, low, mid, high);
    }

    private static int merge(int[] data, int low, int mid, int high) {
        int res = 0;
        int i = 0;
        int p1 = low;
        int p2 = mid + 1;
        int[] temp = new int[high - low + 1];

        while (p1 <= mid && p2 <= high) {
            if (data[p1] < data[p2]) {
                res++;
                System.out.println("[ " + data[p1] + " , " + data[p2] + " ]");
                temp[i++] = data[p1++];
            } else {
                temp[i++] = data[p2++];
            }
        }
        while (p1 <= mid) {
            temp[i++] = data[p1++];
        }
        while (p2 <= high) {
            temp[i++] = data[p2++];
        }

        for (i = 0 ; i < temp.length ; i++) {
            data[low + i] = temp[i];
        }
        return res;
    }
}

执行结果

[ 1 , 3 ]
[ 1 , 5 ]
[ 3 , 5 ]
[ 2 , 4 ]
[ 1 , 2 ]
[ 3 , 4 ]
6

Process finished with exit code 0

---

完

#归并排序 #排序 #小和问题 #逆序对问题