使用合并排序计数反转-意外结果

鸿ne

这段代码对于少量元素会产生正确的结果,但是我不知道为什么对于大量数字(100,000个元素)而言,结果是不正确的。例如,这是Coursera中的100,000个整数文本文件我已经从我的python代码中获得了正确的结果。但是我想弄清楚为什么这个php代码不正确。输出是2407905288的2397819672 intead。

$raw_input = file_get_contents($argv[1]);

$arr_input = explode("\n",trim($raw_input));

$count = 0.0;

function merge_sort($a)
{
    if(count($a) <2) return $a;
    $hl = count($a)/2;
    return merge(merge_sort(array_slice($a, 0, $hl)), merge_sort(array_slice($a, $hl)));

}

function merge($l, $r)
{
    global $count;
    $result = array();
    $i = $j = 0;

    while($i < sizeof($l) && $j < sizeof($r))
    {
        if($l[$i] < $r[$j])
        {
            $result[] =$l[$i];
            $i++;
        }
        else
        {
            $result[] =$r[$j];
            $count+= (sizeof($l) - $i);
            $j++;
        }
    }

    while($i <sizeof($l))
    {
        $result[] = $l[$i];
        $i++;
    }

    while($j <sizeof($r))
    {
        $result[] = $r[$j];
        $j++;
    }
    return $result;
}

$sorted = merge_sort($arr_input);

print $count . "\n";
kkzxak47

我不认为这是与最大整数值相关的问题,因为我在python中也遇到了此问题。如果我的代码的最后一部分是

f = open('IntegerArray.txt')
unsorted = list()
for line in f:
    unsorted.append(line)
merge_sort(unsorted)

如果我的代码的最后一部分是

f = open('IntegerArray.txt')
unsorted = list()
for line in f:
    unsorted.append(int(line))
merge_sort(unsorted)

你能找出区别吗?这就是答案所在。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章