[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);