[摘要]本篇文章给大家带来的内容是关于php如何实现数组归并排序并计算逆序对的个数（代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。在数组中的两个数字，如果前面一个数字大于后面的数字，...
本篇文章给大家带来的内容是关于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,74
6,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,43
3,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575];
$m=InversePairs($A);
var_dump($m);以上就是php如何实现数组归并排序并计算逆序对的个数（代码）的详细内容，更多请关注php中文网其它相关文章！
微信
分享
网站建设是一个广义的术语，涵盖了许多不同的技能和学科中所使用的生产和维护的网站。
关键词：php如何完成数组归并排序并计算逆序对的个数（代码）