在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數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 $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如何實現數組歸并排序并計算逆序對的個數（代碼）的詳細內容，PHP教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。