辽宁网站建设找哪家,外国设计网站推荐,廊坊网站建,wordpress+短视频主题之前的文章里有写归并排序的最小和问题#xff08;归并排序-最小和-CSDN博客#xff09;#xff0c;逆序对问题其实跟最小和问题的本质一样#xff1a;
逆序对#xff1a;给定一个数据#xff0c;从左往右#xff0c;从第一个数开始#xff0c;它右边每一个比它小的都…之前的文章里有写归并排序的最小和问题归并排序-最小和-CSDN博客逆序对问题其实跟最小和问题的本质一样
逆序对给定一个数据从左往右从第一个数开始它右边每一个比它小的都能和它组成一个逆序对比如{3, 4, 1, 2}对于3来说右边比它小的只有1,2对于4来说比它小的也只有1,2对于1和2来说右边没有比它们自己小的所以最终的逆序对是4而{3, 4, 2,1}的逆序对则是5因为2的右边有一个1比它小
最小和的解法过程中是寻找每一个数右边数组中比左边数组中大的数据有几个而逆序对则寻找每一个数右边数组中比左边数组中小的数据有几个只是在比较和拷贝的时候要从数组的最后一位开始而不是下标为0的位置开始由于思想同最小和是差不多的这里就不细讲了直接看代码
public static void main(String[] args) {int arr[] new int[]{3, 4, 1, 2};int length arr.length;System.err.println(process(arr, 0, length - 1));for (int i 0; i length; i) {System.err.println(arr[i]);}}private static int process(int arr[], int start, int end) {if (start end) {return 0;}int middle start ((end - start) 1);//0 1return process(arr, start, middle) process(arr, middle 1, end) merge(arr, start, middle, end);}/*** 核心逻辑就是对于右边数组中要严格比左边数组的数据小满足条件就拷贝左边的数据* param arr* param start* param middle* param end* return*/private static int merge(int arr[], int start, int middle, int end) {int result 0;int[] help new int[end - start 1];int i help.length - 1;int index1 middle;int index2 end;while (index1 start index2 middle 1) {result result (arr[index2] arr[index1] ? (index2 - middle) : 0);help[i--] arr[index2] arr[index1] ? arr[index1--] : arr[index2--];}while (index1 start) {help[i--] arr[index1--];}while (index2 middle 1) {help[i--] arr[index2--];}int length help.length;for (int i1 0; i1 length; i1) {arr[start i1] help[i1];}return result;}
