How to implement array merge sorting and count the number of reverse-order pairs in PHP (code)

The content of this article is about how to implement array merging and sorting in PHP and calculate the number of reverse-order pairs (code). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. help.

Two numbers in the array, if the previous number is greater than the following number, then the two numbers form a reverse-order pair. Input an array and find the total number of reverse-order pairs P in the array. And output the result of P modulo 1000000007. That is, output P 00000007
1. Array merge sort
2. Merge sort When comparing the sizes of elements in the left and right heap arrays, count and compare backwards, because the left heap is the first if it is worse than the right heap The first is the largest, then it is larger than everything in the right heap

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]

The temporary array is copied back to the original array

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

The above is the detailed content of How to implement array merge sorting and count the number of reverse-order pairs in PHP (code). For more information, please follow other related articles on the PHP Chinese website!