php如何实现数组归并排序并计算逆序对的个数（代码）
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如何实现数组归并排序并计算逆序对的个数（代码）所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
