题解 | #数组中的逆序对#

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param data int整型一维数组 
 * @return int整型
 */
function InversePairs( $data )
{
    // write code here
    if (empty($data)) return 0;
    return InversePairsCore($data,0, count($data)-1);
}
function InversePairsCore(&$data, $start, $end) {
    if ($start == $end) return 0;
    $mid = ($start + $end) >> 1;
    $leftCount = InversePairsCore($data, $start, $mid);
    $rightCount = InversePairsCore($data, $mid+1, $end);
    $count = mergeArray($data, $start, $mid, $end);
    return ($leftCount + $rightCount + $count)%1000000007;
}
function mergeArray(&$data, $start, $mid, $end) {
    $count = 0;
    $i = $start;
    $j = $mid + 1;
    $tmp = [];
    while ($i <= $mid && $j <= $end) {
        if ($data[$i] > $data[$j]) {
            $tmp[] = $data[$j++];
            $count += $mid - $i + 1;
        } else {
            $tmp[] = $data[$i++];
        }
//         if ($data[$i] > $data[$j]) {
//             $tmp[] = $data[$i++];
//             $count += $end - $j + 1; 
//         } else {
//             $tmp[] = $data[$j++];
//         }
    }
    while ($i <= $mid) {
        $tmp[] = $data[$i++];
    }
    while($j <= $end) {
        $tmp[] = $data[$j++];
    }
    for ($i = 0; $i < count($tmp);$i++) {
        $data[$start + $i] = $tmp[$i];
    }
    return $count;
}