|
|
<
操纵合并排序思惟
那题出有看懂，转去久存
(a) 把少度为4的数组合成成两个少度为2的子数组；
(b) 把少度为2的数组合成成两个少度为1的子数组；
(c) 把少度为1的子数组 兼并、排序并统计顺序对 ；
(d) 把少度为2的子数组兼并、排序，并统计顺序对；
正在上图（a）战（b）中，我们先把数组合成成两个少度为2的子数组，再把那两个子数组别离拆成两个少度为1的子数组。接下去一边兼并相邻的子数组，一边统计顺序对的数量。正在第一对少度为1的子数组{7}、{5}中7年夜于5，因而（7,5）构成一个顺序对。一样正在第两对少度为1的子数组{6}、{4}中也有顺序对（6,4）。因为我们曾经统计了那两对子数组内乱部的顺序对，因而需求把那两对子数组 排序 如上图（c）所示， 免得正在当前的统计过程当中再反复统计。
接下去我们统计两个少度为2的子数组子数组之间的顺序对。兼并子数组并统计顺序对的历程以下图以下图所示。
我们先用两个指针别离指背两个子数组的结尾，并每次比力两个指针指背的数字。假如第一个子数组中的数字年夜于第两个数组中的数字，则组成顺序对，并且顺序对的数量即是第两个子数组中盈余数字的个数，以下图（a）战（c）所示。假如第一个数组的数字小于或即是第两个数组中的数字，则没有组成顺序对，如图b所示。每次比力的时分，我们皆把较年夜的数字从后背往前复造到一个帮助数组中，确保 帮助数组（记为copy） 中的数字是递删排序的。正在把较年夜的数字复造到帮助数组以后，把对应的指针背前挪动一名，接下去停止下一轮比力。
历程：先把数组朋分成子数组，先统计出子数组内乱部的顺序对的数量，然后再统计出两个相邻子数组之间的顺序对的数量。正在统计顺序对的过程当中，借需求对数组停止排序。假如对排序算法很熟悉，我们没有易发明那个历程理想上便是合并排序。参考代码以下：
[code]public class Solution { //定义一个成员变量用去统计顺序对的数量 int count; public int InversePairs(int [] array) { //特别输进战鸿沟输进 if(array==null||array.length=end) return; //假如出有停止便递回挪用持续拆分 this.divide(array,tempArray,start,middle); this.divide(array,tempArray,middle+1,end); this.merge(array,tempArray,start,end); } /*那个办法用去对两个曾经排序的子数组停止兼并，将其从头排序并且记载兼并时发生的顺序对数量，将正在start战end范畴以内的数组停止兼并， 明显那个两个数组的分界面是(start+end)/2*/ public void merge(int[] array,int[] tempArray,int start,int end){ int middle=(start+end)/2; //左边子数组是从start~middle；右边子数组是从middle+1~end //现将其兼并排序，统计顺序对数量 int leftPoint=start; int rightPoint=middle+1; //了解：每次挪用merge()办法只是对start到end范畴内乱的数据停止排序,因而用tempPoint指针去记载临时数组中加添进的数字的地位 int tempPoint=start; //对两个子数组停止遍历，曲到一个数组遍历结束，避免数组会见越界 while(leftPoint |
1、本网站属于个人的非赢利性网站，转载的文章遵循原作者的版权声明，如果原文没有版权声明，按照目前互联网开放的原则，我们将在不通知作者的情况下，转载文章;如果原文明确注明“禁止转载”，我们一定不会转载。如果我们转载的文章不符合作者的版权声明或者作者不想让我们转载您的文章的话，请发帖留言提供原创证明，我们将积极配合您！
2、本网站转载文章仅为传播更多信息之目的，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所提供信息的准确性及可靠性，但不保证信息的正确性和完整性，且不对因信息的不正确或遗漏导致的任何损失或损害承担责任。
3、任何透过本网站网页而链接及得到的资讯、产品及服务，本网站概不负责，亦不负任何法律责任。
4、本网站所刊发、转载的文章，其版权均归原作者所有，如其他媒体、网站或个人从本网下载使用，请在转载有关文章时务必尊重该文章的著作权，保留本网注明的“稿件来源”，并自负版权等法律责任。
|
闲聊
1320 人阅读
|
0 人回复
