博文
Use MergeSort to Count Inversions by Perl
||
上篇博文实现了归并排序，现将其修改既能排序，又能对逆序数计数。
https://blog.sciencenet.cn/blog-752323-630772.html
上一篇：Realize MergeSort with Perl
下一篇：Install Perl Modules on Windows
#!usr/bin/perl -w
if(!open MYFILE,'/Users/Sky/Desktop/data.txt')
{
print "Cannot open the source file!";
}
$t=0;
foreach(<MYFILE>)
{
$a[$t]=$_;
$t++;
}
close(MYFILE);
$a=@a;
print &MergeSort(0,$a-1,0,@a);
sub MergeSort
{
my($f,$r,$invers,@array)=@_;
my $mi;
if($f<$r)
{
$mi=int(($f+$r)/2);
($invers,@array)=&MergeSort($f,$mi,$invers,@array);
($invers,@array)=&MergeSort($mi+1,$r,$invers,@array);
($invers,@array)=&Merge_and_Count($f,$mi,$r,$invers,@array);
}
return $invers,@array;
}
sub Merge_and_Count
{
my($f,$mi,$r,$inv,@arra)=@_;
$i=$f;
$j=$mi+1;
$k=0;
my @arr=();
while($i<=$mi && $j<=$r)
{
if($arra[$i]<=$arra[$j])
{
$arr[$k++]=$arra[$i++];
}else
{
$arr[$k++]=$arra[$j++];
$inv=$inv+($mi-$i+1);
}
}
while($i<=$mi)
{
$arr[$k++]=$arra[$i++];
}
while($j<=$r)
{
$arr[$k++]=$arra[$j++];
}
$i=$f;
foreach(@arr)
{
$arra[$i++]=$_;
}
return $inv,@arra;
}
源文件merge_inversions.pl 对不起，由于本人水平有限，该程序处理小规模数据时，可以执行，但是不知道怎么回事，大规模数据等了很长时间也没出结果。
https://blog.sciencenet.cn/blog-752323-630772.html
上一篇：Realize MergeSort with Perl
下一篇：Install Perl Modules on Windows
