1

我有一堆裁判。就像是

$a[0] = [qw( 1 2 3 4 )];
$a[1] = [qw( a b c d )];

, 1, 2,实际上是用于导航的网站面包屑（3, , , ）。4HomeProfileContact-usContact-me-specifically

现在，我必须对这个阶梯进行排序（遗憾的是，在 perl 5.8 中使用稳定排序不是一种选择）

排序标准是

  1. 梯子的深度
  2. 如果两个梯子的深度相同，则根据它们的索引对其进行排序。

例如，如果数组最初包含

$a[0] = [qw( 1 2 3 4 )];
$a[1] = [qw( 1 2 3 )];

然后在排序之后，数组应该包含

$a[0] = [qw( 1 2 3 )];
$a[1] = [qw( 1 2 3 4 )];

但是如果数组是这样的： -

$a[0] = [qw( 1 2 3 )];
$a[1] = [qw( a b c )];

然后排序后，

$a[0] = [qw( 1 2 3 )];
$a[1] = [qw( a b c )];

我无法让它以我尝试过的方式工作。

my @sorted_array = sort { @$b <=> @$a || $a <=> $b } @a;

有人可以帮助我吗？

4

3 回答 3

4

您的数据结构（链表）的描述和您的sort例程（arrayrefs）中的实现并不完全吻合；我将假设后者。

通过将位置排序作为次要标准，可以使不稳定的排序变得稳定：

sort { normally or by_index } @stuff

通常，您似乎想比较数组长度。为了能够测试索引，您必须以某种方式使当前元素的索引可用。您可以通过两种方式做到这一点：

  1. 进行 Schwartzian 变换，并用索引注释每个元素。这很愚蠢。
  2. 对索引进行排序，而不是对元素进行排序。

这看起来像：

my @sorted_indices =
  sort { @{ $array[$b] } <=> @{ $array[$a] } or $a <=> $b } 0 .. $#array;
my @sorted = @array[@sorted_indices]; # do a slice

您之前所做的$a <=> $b是比较引用。这不能保证做任何有意义的事情。

测试sort：

use Test::More;
my @array = (
  [qw/1 2 3/],
  [qw/a b c/],
  [qw/foo bar baz qux/],
);
my @expected = (
  [qw/foo bar baz qux/],
  [qw/1 2 3/],
  [qw/a b c/],
);

...; # above code
is_deeply \@sorted, \@expected;
done_testing;
于 2013-07-11T13:10:32.690 回答
2

您的代码不起作用，因为您希望$a并将$b元素的值包含在一个位置 ( @$b <=> @$a) 中，并将元素的索引包含在另一个位置 ( $a <=> $b) 中。

您需要比较中的索引，因此您的比较功能将需要索引。

通过将数组的索引传递给sort，您可以访问索引和这些索引处的值，因此您的代码将包括

sort { ... } 0..$#array;

完成排序后，我们要检索这些索引的元素。为此，我们可以使用

my @sorted = map $array[$_], @sorted_indexes;

或者

my @sorted = @array[ @sorted_indexes ];

总之，我们得到：

my @sorted =
   map $array[$_],
    sort { @{ $array[$a] } <=> @{ $array[$b] } || $a <=> $b }
      0..$#array;

或者

my @sorted = @array[
   sort { @{ $array[$a] } <=> @{ $array[$b] } || $a <=> $b }
     0..$#array
];
于 2013-07-11T13:29:42.290 回答
1

我认为我们需要清理您的排序算法。你说：

  1. 梯子的深度
  2. 根据它们的索引对它们进行排序。

这是一个例子：

$array[0] = [ qw(1 a b c d e) ];
$array[2] = [ qw(1 2 b c d e) ];
$array[3] = [ qw(a b c) ];
$array[4] = [ qw(a b c d e) ];

您希望它们以这种方式排序：

$array[3] = [ qw(a b c) ];
$array[2] = [ qw(1 2 b c d e) ];
$array[0] = [ qw(1 a b c d e) ];
$array[4] = [ qw(a b c d e) ];

那是对的吗？

那这个呢？

$array[0] = [ qw(100, 21, 15, 32) ];
$array[1] = [ qw(32,  14, 32, 20) ];

按数字排序，$array[1]应该是 before $array[0]，但按字符串排序，$array[0]是 before $array[1]。

此外，您注意到在查看数组的第二个元素之前，我无法判断$array[0]应该在之前还是之后。$array[1]

这使得在单行函数上进行排序非常困难。即使你能以某种方式减少它，它也会让别人很难分析你在做什么，或者让你调试语句。

幸运的是，您可以将整个子例程用作排序例程：

use warnings;
use strict;
use autodie;
use feature qw(say);
use Data::Dumper;

my @array;
$array[0] = [ qw(1 2 3 4 5 6) ];
$array[1] = [ qw(1 2 3) ];
$array[2] = [ qw(a b c d e f) ];
$array[3] = [ qw(0 1 2) ];

my @sorted_array = sort sort_array @array;
say Dumper \@sorted_array;

sub sort_array {
    #my $a = shift;   #Array reference to an element in @array
    #my $b = shift;   $Array reference to an element in @array

    my @a_array = @{ $a };
    my @b_array = @{ $b };

    #
    #First sort on length of arrays
    #
    if ( scalar  @a_array ne scalar  @b_array ) {
        return scalar @a_array <=> scalar @b_array;
    }

    #
    # Arrays are the same length. Sort on first element in array that differs
    #
    for my $index (0..$#a_array ) {
        if ( $a_array[$index] ne $b_array[$index] ) {
            return $a_array[$index] cmp $b_array[$index];
        }
    }
    #
    # Both arrays are equal in size and content
    #
    return 0;
}

这将返回：

$VAR1 = [
          [
            '0',
            '1',
            '2'
          ],
          [
            '1',
            '2',
            '3'
          ],
          [
            '1',
            '2',
            '3',
            '4',
            '5',
            '6'
          ],
          [
            'a',
            'b',
            'c',
            'd',
            'e',
            'f'
          ]
        ];
于 2013-07-11T13:48:59.183 回答