根据已排序数组对数组进行排序

Question

我有一个参考数组，其中包含所有可能的元素，并按照不同于字母数字排序的自定义顺序进行排序。例如：

@ref_array = ('one','two','three','four','five','six');

现在所有的输入数组都需要按照参考数组的顺序进行排序。输入数组将始终是参考数组的子集。

@in1 = ('three','one','five');  # Input
@out1 = ('one','three','five'); # Desired Output

@in2 = ('six','five','four','three','two','one'); # Input
@out2 = ('one','two','three','four','five','six') # Desired Output

- jkshah

Answer 1

my %h = map { $ref_array[$_] => $_ } 0 .. $#ref_array;

my @out1 = @ref_array[ sort { $a <=> $b } @h{@in1} ];
my @out2 = @ref_array[ sort { $a <=> $b } @h{@in2} ];

%h 存储键值对，例如 one => 0, two => 1 等。

@h{@in1} 是 2,0,4 的哈希切片，将被排序，数组切片 @ref_array[0,2,4] 是 one, three, five。

- mpapec

---

好的！这比我的解决方案更加优雅。（尽管 请 开始解释你的答案！） - amon

@amon 如果 OP 要求解释，我会写解释，因为我写得比较慢，而且不够雄辩。 - mpapec

由于 Perl 中缺乏类型系统，因此需要两组比较运算符：eq vs. ==，cmp vs <=>。Ruby 和 Perl6 没有这个问题，并且可以提供通用比较。在 Perl5 中，字符串排序是一个合理的默认值。但你可以自由定义自己的排序方法，例如 sub numsort { sort { $a <=> $b } @_ }。 - amon

针对@amon的第一个观点，您可以在发布代码后编写解释。请记住，SO上的答案不仅适用于OP，还适用于未来任何其他人着陆此页面的人。话虽如此，非常好的解决方案。 - ThisSuitIsBlackNot

@JKShah 所有的功劳归功于mpapec！你的代码可能看起来更短，但是它不够高效，因为你使用了更昂贵的哈希访问。相比之下，mpapec的代码看起来非常优化。不要感到困惑；相反，学会理解它们的含义！perlreftut 是一个很好的开始。 - amon

Answer 2

这并不复杂。

步骤1，我们需要一个从您的值到Perl可以排序的某些键的映射，例如数字。我们可以使用自定义排序数组中元素的索引，如下所示：

my %custom_value = map { $ref_array[$_] => $_ } 0 .. $#ref_array;

第二步，我们使用上述值之一作为键对您的输入执行Schwartzian变换：

my @out =
  map  { $_->[1] }
  sort { $a->[0] <=> $b->[0] }
  map  {[ $custom_value{$_} => $_ ]}
       @in;

- amon

Answer 3

对于使用小整数键进行排序，基数排序通常是更快的解决方案，具有O(N)的复杂度：

use Sort::Key::Radix qw(ukeysort);

my @ref = ('one','two','three','four','five','six');
my %ref = map { $ref[$_] => $_ } 0..$#ref;

my @out = ukeysort { $ref{$_} } @in;

或者你也可以使用廉价的O(N)计数排序：

my %ref;
$ref{$_}++ for @in;
no warnings 'uninitialized';
my @out = map { ($_) x $ref{$_} } @ref;

- salva

---

在第二个代码块中，您可能想要将赋值给@out而不是$out，并且可能需要在最后一行中加入no warnings "uninitialized"。 - Slaven Rezic

Answer 4

所有提出的解决方案都展示了具有 O(NlogN) 时间复杂度的排序。有一种方法可以在实际不进行排序的情况下以 O(N) 的时间复杂度完成它。

sub custom_usort {
    my %h;
    @h{@_} = ();
    grep exists $h{$_}, ('one','two','three','four','five','six');
}

编辑:

如果输入可以有多个值，则有以下解决方案：

sub custom_sort {
    my %h;
    $h{$_}++ for @_;
    no warnings 'uninitialized';
    map {($_) x $h{$_}} ('one','two','three','four','five','six');
}

- Hynek -Pichi- Vychodil

---

当@in具有重复元素时，该解决方案会失败。 - salva

@salva，问题中没有这样的例子。 - Hynek -Pichi- Vychodil