[PHP] 算法-数组归并排序并计算逆序对的个数的PHP实现

发布时间：2020-05-25 03:10:59 所属栏目：PHP 来源：互联网

导读：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%10000000071.数组归并排序2.归并排序比较左右两个堆数组中的元素大小时，进行计

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 
1.<span style="color: #000000">数组归并排序

2.<span style="color: #000000">归并排序比较左右两个堆数组中的元素大小时，进行计数，倒着比较，因为左堆倒第一如果比右堆倒第一大，那么就比右堆的所有都大

mergeSort

<span style="color: #0000ff">if left<<span style="color: #000000">right

mid=[(p+r)/2<span style="color: #000000">]

mergeSort(arr,left,mid,<span style="color: #000000">temp)

mergeSort(arr,mid+1,right,<span style="color: #000000">temp)

merge(arr,<span style="color: #000000">temp)

merge(arr,<span style="color: #000000">temp)

i=<span style="color: #000000">mid

j=<span style="color: #000000">right

t=<span style="color: #000000">right

<span style="color: #0000ff">while i<=mid && j<=<span style="color: #000000">right

<span style="color: #0000ff">if arr[i<<span style="color: #000000">arr[j]

temp[t--]=arr[i--<span style="color: #000000">]

<span style="color: #0000ff">else

<span style="color: #008080">count+=mid-i+1<span style="color: #000000">

temp[t--]=arr[j--<span style="color: #000000">]

<span style="color: #0000ff">while i<=<span style="color: #000000">mid

temp[t--]=<span style="color: #000000">arr[i]

<span style="color: #0000ff">while j<=<span style="color: #000000">right

temp[t--]=<span style="color: #000000">arr[j]

临时数组重新复制回原数组

InversePairs(=0=,()-1,,%=1000000007 mergeSort(&,,,& (< =((+)/2 mergeSort(,, mergeSort(,+1, merge(, merge(&,& = =+1 =0 (<= && <= ([]<[ [++]=[++

                    </span><span style="color: #800080"&gt;$num</span>+=<span style="color: #800080"&gt;$mid</span>-<span style="color: #800080"&gt;$i</span>+1<span style="color: #000000"&gt;;
                    </span><span style="color: #008000"&gt;//</span><span style="color: #008000"&gt;13.右堆赋给临时数组,索引加1</span>
                    <span style="color: #800080"&gt;$temp</span>[<span style="color: #800080"&gt;$t</span>++]=<span style="color: #800080"&gt;$A</span>[<span style="color: #800080"&gt;$j</span>++<span style="color: #000000"&gt;];
            }
    }
    </span><span style="color: #008000"&gt;//</span><span style="color: #008000"&gt;14.左堆剩余的全部加进临时数组</span>
    <span style="color: #0000ff"&gt;while</span>(<span style="color: #800080"&gt;$i</span><=<span style="color: #800080"&gt;$mid</span><span style="color: #000000"&gt;){
            </span><span style="color: #800080"&gt;$temp</span>[<span style="color: #800080"&gt;$t</span>++]=<span style="color: #800080"&gt;$A</span>[<span style="color: #800080"&gt;$i</span>++<span style="color: #000000"&gt;];
    }
    </span><span style="color: #008000"&gt;//</span><span style="color: #008000"&gt;15.右堆剩余全部加进临时数组</span>
    <span style="color: #0000ff"&gt;while</span>(<span style="color: #800080"&gt;$j</span><=<span style="color: #800080"&gt;$right</span><span style="color: #000000"&gt;){
            </span><span style="color: #800080"&gt;$temp</span>[<span style="color: #800080"&gt;$t</span>++]=<span style="color: #800080"&gt;$A</span>[<span style="color: #800080"&gt;$j</span>++<span style="color: #000000"&gt;];
    }
    </span><span style="color: #008000"&gt;//</span><span style="color: #008000"&gt;16.临时数组的元素重新赋回原数组</span>
    <span style="color: #0000ff"&gt;for</span>(<span style="color: #800080"&gt;$i</span>=0;<span style="color: #800080"&gt;$i</span><<span style="color: #800080"&gt;$t</span>;<span style="color: #800080"&gt;$i</span>++<span style="color: #000000"&gt;){
            </span><span style="color: #800080"&gt;$A</span>[<span style="color: #800080"&gt;$left</span>+<span style="color: #800080"&gt;$i</span>]=<span style="color: #800080"&gt;$temp</span>[<span style="color: #800080"&gt;$i</span><span style="color: #000000"&gt;];
    }

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

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!