Comment implémenter le tri par fusion de tableaux et compter le nombre de paires dans l'ordre inverse en PHP (code)

Le contenu de cet article explique comment implémenter le tri par fusion de tableaux et calculer le nombre de paires d'ordre inverse (code) en PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. à vous.

Deux nombres dans le tableau, si le premier nombre est supérieur au dernier nombre, alors les deux nombres forment une paire d'ordre inverse. Saisissez un tableau et recherchez le nombre total de paires d’ordre inverse P dans le tableau. Et affichez le résultat de P modulo 1000000007. C'est-à-dire que la sortie P%1000000007
1. Tri par fusion de tableaux
2. Tri par fusion lorsque vous comparez les tailles des éléments dans les tableaux de tas gauche et droit, comptez et comparez à rebours, car le tas de gauche est le premier s'il est. est pire que le tas de droite Le premier est le plus grand, puis il est plus grand que tout ce qui se trouve dans le tas de droite

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]

Le tableau temporaire est recopié dans le tableau d'origine

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!