希望小学学校网站建设方案,网络商城推广,大设计师论坛网页设计,如何自己做网页求逆序对问题用归并排序的时间复杂度比暴力算法更低。假设有一个数组{8#xff0c;1#xff0c;2#xff0c;5#xff0c;7#xff0c;4#xff0c;3#xff0c;6}首先归并排序第一次对数组进行分割 8 1 2 5 7 4 3 6二次分割 8 1 25 74 3…求逆序对问题用归并排序的时间复杂度比暴力算法更低。假设有一个数组{81257436}首先归并排序第一次对数组进行分割 8 1 2 5 7 4 3 6二次分割 8 1 25 74 36三次分割 8 1 2 5 7 4 3 6第一次合并 18 25 74 36 reorder[1]2, order[1]2//用reorder[i]来记录第i次合并中存在的逆序对数,order[i]来记录第i次合并中存在的顺序对数。第二次合并 1258 3467 reorder[2]5, order[2]3第三次合并 12345678 reorder[3]6, order[3]10那么数组{81257436}中存在的逆序对就等于reorder[1]reorder[2]reorder[3]13将数组{81257436}每2^2个为一组进行翻转{52186347}首先归并排序第一次对数组进行分割 5 2 1 8 6 3 4 7二次分割 5 2 18 63 47三次分割 5 2 1 8 6 3 4 7第一次合并 25 18 36 47 reorder[1]2, order[1]2第二次合并 1258 3467 reorder[2]3, order[2]5第三次合并 12345678 reorder[3]6, order[3]10那么数组{52186347}中存在的逆序对就等于reorder[1]reorder[2]reorder[3]11由此我们可以观察到对数组每2^2个进行翻转时reorder[1]和order[1]进行了互换,reorder[2]和order[2]亦是如此。所以对数组每2^i个进行翻转时我们可以把1~i的reorder和order数组元素互换即可继续通过计算reorder数组的累加和来求得数组的逆序对数。import java.util.ArrayList;import java.util.Scanner;public class Main {public static void main(String[] args){Scanner sc new Scanner(System.in);int n sc.nextInt();int N 1 n;int[] a new int[N];int[] b new int[N];//用来存储数组的逆序,对逆序的数组进行一次归并排序可以直接得到order数组int[] order new int[n 1];//为了便于计算所以设置order下标是1~n因此数组大小为n1int[] reorder new int[n 1];for (int i 0; i N; i){a[i] sc.nextInt();b[N - i - 1] a[i];}MergeSort(a, 0, N - 1, reorder, n);//对整个数组进行归并排序n表示对reorder[1]~reorder[n]进行初始化MergeSort(b, 0, N - 1, order, n);//对整个逆序数组进行归并排序完成对order[1]~order[n]的初始化int m sc.nextInt();while(m-- 0){int count 0;int q sc.nextInt();for (int i 1; i q; i) //像之前讲的将1~q的reorder[i]和order[i]进行互换{int temp reorder[i];reorder[i] order[i];order[i] temp;}for (int i 1; i n; i){count reorder[i];//累加reorder数组求得对数组中每2^q个元素进行翻转后的逆序对数}System.out.println(count);}}public static void MergeSort(int[] a , int left, int right, int[] reorder, int index){if(left right){int mid (right left) / 2;MergeSort(a, left, mid, reorder,index - 1);MergeSort(a, mid 1, right, reorder,index -1);if(a[mid] a[mid1])//如果a[mid]a[mid1]则原数组有序不需要合并Merge(a, left, right,reorder, index);}}public static void Merge(int[] a, int left, int right,int[] reorder, int index)//index表示对reorder[index]进行初始化{int mid (right left) / 2;int Length1 mid - left 1;int Length2 right - mid;int[] l new int[Length1];//存储a[left]~a[mid]int[] r new int[Length2];//存储a[mid1]~a[right]System.arraycopy(a, left, l, 0, Length1);//对l进行初始化System.arraycopy(a, mid 1, r, 0, Length2);//对r进行初始化int i 0;int j 0;int c 0;int k left;while(i Length1 j Length2){if(l[i] r[j]){a[k] l[i];i;}else{a[k] r[j];j;c Length1 - i;//当l[i]r[j]时因为l是递增序列所以l[i]~l[Length1-1]均r[j]所以有Length1-i个元素大于r[j]}k;}System.arraycopy(l, i, a, k, Length1 - i);//前面归并排序MergeSort中调用Merge合并的条件是a[mid]a[mid1],因为当a[mid]a[mid1]时说明原数组有序无需合并。l[Length1-1]r[Length2-1],即l数组的最大值大于r数组的最大值所以当r中的数全部进入a数组后l数组中仍有剩余。reorder[index] c;}}
