有一个数组，可以包含多达1000个元素。它可以产生的数字范围是1到10 ^ 10。现在我必须找到数组中两个数字之间的最小绝对差。我已经想到了两种算法：
对于第一个，我已经定义了一个二进制搜索函数，它查找排序数组中被插入数字的位置。现在我启动排序数组，只有给定数组的第一个数字，并从第二个元素开始对给定的数组进行迭代。对于每个数字，我在排序的数组中找到它的位置。如果该位置的数字是这个数字，则差值为0，这是最低的数值，所以我退出循环。否则，我在该点将数字插入排序的数组，然后检查该数字与该数组中的前一个和下一个数字之间的差异。然后我存储此结果的最小值和以前的结果，并以此方式继续。
第二：我使用quicksort对数组进行排序。 (范围太大，所以我认为基数排序不会那么有效)。然后我重复一遍，如果两个连续的数字相等，则用0的答案展开，否则存储该数字与之前的数字和先前结果之间的差异的最小值。
哪一个会更有效率？
有没有更好的算法？
Stackoverflow在这方面有很多职位，但是他们没有什么帮助。以下是我在Perl中的代码：
sub position {
my @list = @{$_[0]};
my $target = $_[1];
my ($low,$high) = (0,(scalar @list)-1);
while ($low <= $high) {
$mid = int(($high + $low)/2);
if ( $list[$mid] == $target ) {
return $mid;
}
elsif ( $target < $list[$mid] ) {
$high = $mid - 1;
}
else {
$low = $mid + 1;
}
}
$low;
}
sub max { $_[0] > $_[1] ? $_[0] : $_[1]; }
sub min { $_[0] > $_[1] ? $_[1] : $_[0]; }
$ans = 10_000_000_000;
@numbers = (234,56,1,34...123); #given array
($max,$min) = @num[0,0];
@sorted = ($numbers[0]);
for ( @num[1 .. $#num] ) {
$pos = position(\@sorted,$_);
if ( $sorted[$pos] == $_ ) {
$ans = 0;
last;
}
splice @sorted,$pos,$_;
if ( $#sorted == $pos ) {
$ans = min($_-$sorted[-2],$ans);
}
elsif ( 0 == $pos ) {
$ans = min($sorted[1]-$_,$ans);
}
else {
$ans = min(min(abs($sorted[$pos-1]-$_),abs($sorted[$pos+1]-$_)),$ans);
}
$max = max($_,$max);
$min = min($_,$min);
}
print "$ans\n";
解决方法
你最多有5k个元素。
请注意，sandy bridge处理器具有32KB L1-Cache，假设为4字节整数 – 这意味着它可以包含8192个整数。
我会尽量避免创建额外的数据(除了计数器等等)，并使用相同的数组来做所有事情。这将使得cache-misses的数量非常小，并且可能会超出任何算法。
因此，一个就地快速排序，而不是迭代数组中的元素，可能会比任何其他解决方案更好，无论是缓存高效还是保持O(nlogn)的体面渐近的复杂性。
注意 – 虽然这个解决方案可能会更有效率(至少在理论上)，但是规模还是非常小的，除非你要做这么多的时间，否则你的时间过于优化。
一般提示：当谈到小规模问题(最多5000个元素符合这个标准)时，大O符号通常是不够的。缓存性能通常是这些问题的主要因素。