php如何实现数组归并排序并计算逆序对的个数（代码）

内容导读

收集整理的这篇技术教程文章主要介绍了php如何实现数组归并排序并计算逆序对的个数（代码），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2403字，纯文字阅读大概需要4分钟。

内容图文

本篇文章给大家带来的内容是关于php如何实现数组归并排序并计算逆序对的个数（代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
1.数组归并排序
2.归并排序比较左右两个堆数组中的元素大小时，进行计数，倒着比较，因为左堆倒第一如果比右堆倒第一大，那么就比右堆的所有都大

mergeSort    if left<right        mid=[(p+r)/2]        mergeSort(arr,left,mid,temp)        mergeSort(arr,mid+1,right,temp)        merge(arr,left,mid,right,temp)merge(arr,left,mid,right,temp)    i=mid    j=right    t=right    while i<=mid && j<=right        if arr[i<arr[j]            temp[t--]=arr[i--]        else            count+=mid-i+1            temp[t--]=arr[j--]     while i<=mid        temp[t--]=arr[i]    while j<=right        temp[t--]=arr[j]

临时数组重新复制回原数组

function InversePairs($data){    $num=0;    $temp=array();    mergeSort($data,0,count($data)-1,$temp,$num);    $num%=1000000007;    return $num;}//1.利用分治法思想,递归的切分排序元素function mergeSort(&$A,$left,$right,$temp,&$num){        //2.最左只能小于最右,等于的时候就一个元素,大于是不可能的        if($left<$right){                //3.获取中间的元素                $mid=intval(($left+$right)/2);                //4.递归左半区                mergeSort($A,$left,$mid,$temp,$num);                //5.递归右半区                mergeSort($A,$mid+1,$right,$temp,$num);                //6.合并两个有序数组为一个有序数组                merge($A,$left,$mid,$right,$temp,$num);        }}function merge(&$A,$left,$mid,$right,$temp,&$num){        //7.左堆起始        $i=$left;        //8.右堆起始        $j=$mid+1;        //9.临时数组起始        $t=0;        //10.左右堆数组都没到末尾        while($i<=$mid && $j<=$right){                //11.左堆小于等于右堆时                if($A[$i]<$A[$j]){                        //12.左堆赋给临时数组,索引加1                        $temp[$t++]=$A[$i++];                }else{                        $num+=$mid-$i+1;                        //13.右堆赋给临时数组,索引加1                        $temp[$t++]=$A[$j++];                }        }        //14.左堆剩余的全部加进临时数组        while($i<=$mid){                $temp[$t++]=$A[$i++];        }        //15.右堆剩余全部加进临时数组        while($j<=$right){                $temp[$t++]=$A[$j++];        }        //16.临时数组的元素重新赋回原数组        for($i=0;$i<$t;$i++){                $A[$left+$i]=$temp[$i];        }}$A=[364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575];$m=InversePairs($A);var_dump($m);

以上就是php如何实现数组归并排序并计算逆序对的个数（代码）的详细内容，更多请关注Gxl网其它相关文章！

内容总结

以上是为您收集整理的php如何实现数组归并排序并计算逆序对的个数（代码）全部内容，希望文章能够帮你解决php如何实现数组归并排序并计算逆序对的个数（代码）所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。